1123581321递归算法_线性递归数列例题

全栈程序员-站长 • 2025年10月30日下午6:01 • 未分类 • 阅读 5

1123581321递归算法_线性递归数列例题[BZOJ3231][Sdoi2008]递归数列题目大意给定Ci,i∈[1,k]给定C_i,i\in[1,k]定义若i>k,Ai=Ai−1∗C1+Ai−2∗C2+⋯+Ai−k∗Ck若i>k,A_i=A_{i-1}*C_1+A_{i-2}*C_2+\cdots+A_{i-k}*C_k否则Ai=Bi否则A_i=B_i询问sum(A)n−sum(A)m−1询问sum(A)_n-sum(A

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

[BZOJ3231] [Sdoi2008]递归数列

题目大意
- $给定C_i,i\in[1,k]$
- 定义
  - $若i>k,A_i=A_{i-1}*C_1+A_{i-2}*C_2+\cdots+A_{i-k}*C_k$
  - $否则A_i=B_i$
- $询问sum(A)_n-sum(A)_{m-1}$
- $k\le 15,n,m\le 10^{18}$
题解
$⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ s u m n A n A n - 1 ⋮ A n - k + 1 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ = = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ 100 ⋮ 0 C 1 C 1 1 ⋮ 0 C 2 C 2 0 ⋱ \dots \dots \dots \dots \dots \dots C k C k 000 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ * ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ s u m n - 1 A n - 1 A n - 2 ⋮ A n - k ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ 100 ⋮ 0 C 1 C 1 1 ⋮ 0 C 2 C 2 0 ⋱ \dots \dots \dots \dots \dots \dots C k C k 000 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ n - k * ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ s u m k A k A k - 1 ⋮ A 1 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥$
$\begin{eqnarray*}\begin{bmatrix}sum_n\\A_n\\A_{n-1}\\\vdots\\A_{n-k+1}\end{bmatrix}&=&\begin{bmatrix}1&C_1&C2&\cdots&C_k\\0&C_1&C2&\cdots&C_k\\0&1&0&\cdots&0\\\vdots&\vdots&\ddots&\cdots&0\\0&0&\cdots&\cdots&0\end{bmatrix}*\begin{bmatrix}sum_{n-1}\\A_{n-1}\\A_{n-2}\\\vdots\\A_{n-k}\end{bmatrix}\\&=&\begin{bmatrix}1&C_1&C2&\cdots&C_k\\0&C_1&C2&\cdots&C_k\\0&1&0&\cdots&0\\\vdots&\vdots&\ddots&\cdots&0\\0&0&\cdots&\cdots&0\end{bmatrix}^{n-k}*\begin{bmatrix}sum_{k}\\A_{k}\\A_{k-1}\\\vdots\\A_{1}\end{bmatrix}\end{eqnarray*}$
CODE

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/194755.html原文链接：https://javaforall.net

赞 (0)

0 0

关于作者

全栈程序员-站长

133.5K 文章

3 粉丝

本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”

linux常用命令修改文件权限_使用vim在指定目录下创建文件

上一篇 2025年10月30日下午5:43

STM32使用LWIP库新建tcp_sever

下一篇 2025年10月30日下午6:15

L2-029 特立独行的幸福

L2-029 特立独行的幸福原题链接对一个十进制数的各位数字做一次平方和，称作一次迭代。如果一个十进制数能通过若干次迭代得到 1，就称该数为幸福数。1 是一个幸福数。此外，例如 19 经过 1 次迭代得到 82，2 次迭代后得到 68，3 次迭代后得到 100，最后得到 1。则 19 就是幸福数。显然，在一个幸福数迭代到 1 的过程中经过的数字都是幸福数，它们的幸福是依附于初始数字的。例如 82、68、100 的幸福是依附于 19 的。而一个特立独行的幸福数，是在一个有限的区间内不依附于任何其它数字的；其独立性就是依附于它的的幸福数

全栈程序员-站长
2022年8月9日
7
manifest文件使用(manifest文件作用)

解决难以打开MANIFEST文件的问题打开MANIFEST文件的麻烦MicrosoftNotepad已删除你尝试加载MANIFEST文件并收到错误，例如“%%os%%无法打开MANIFEST文件扩展名”。通常情况下，这意味着MicrosoftNotepad没有安装在%%os%%上。由于您的操作系统不知道如何处理此文件，因此无法通过双击将其打开。提示：如果你…

全栈程序员-站长
2022年4月11日
187
html静态网页设计代码_静态网页设计心得

html静态网页设计代码_静态网页设计心得第一周：HTML写静态网页1.HTML理论介绍及常用格式（1）.HTML主体格式<!DOCTYPEhtml><html> <head> <metacharset="utf-8"/> <title></title> </head> <body> &

全栈程序员-站长
2026年2月7日
4
openclaw

疯了疯了！鹅厂上门安装龙虾（OpenClaw）了！附保姆级教程

疯了疯了！鹅厂上门安装龙虾（OpenClaw）了！附保姆级教程

Ai探索者
2026年3月13日
3
Unittest测试框架基本使用[通俗易懂]

Unittest测试框架基本使用[通俗易懂]unittest单元测试

全栈程序员-站长
2022年10月14日
4
计算机网络知识汇总（超详细整理）

计算机网络知识汇总（超详细整理）为了准备期末考试，同时也是为了之后复习方便，特对计算机网络的知识进行了整理。本篇内容大部分是来源于我们老师上课的ppt。而我根据自己的理解，将老师的PPT整理成博文的形式以便大家复习查阅，同时对于一些不是很清楚的地方，我去查阅了相关资料进行补充，当然也会有部分个人看法夹带其中来帮助大家理解。

全栈程序员-站长
2022年6月14日
23

发表回复

关注全栈程序员社区公众号