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

全栈程序员-用户IM • 2022年9月12日上午8:46 • 未分类

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

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

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

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权正版激活】： 官方授权正版激活支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)

全栈程序员-用户IM

activity(工作流）初步学习记录

activity(工作流）初步学习记录1.概念工作流(Workflow)，就是“业务过程的部分或整体在计算机应用环境下的自动化”，它主要解决的是“使在多个参与者之间按照某种预定义的规则传递文档、信息或任务的过程自动进行，从而实现某个预期

全栈程序员-用户IM
2022年7月4日
图论（二）：图的四种最短路径算法

图论（二）：图的四种最短路径算法本文总结了图的几种最短路径算法的实现：深度或广度优先搜索算法，弗洛伊德算法，迪杰斯特拉算法，Bellman-Ford算法1），深度或广度优先搜索算法（解决单源最短路径）从起始结点开始访问所有的深度遍历路径或广度优先路径，则到达终点结点的路径有多条，取其中路径权值最短的一条则为最短路径。下面是核心代码：voiddfs(intcur,intdst){/

全栈程序员-用户IM
2022年6月4日
pycharm的最新版本_pycharm最新版本是多少

pycharm的最新版本_pycharm最新版本是多少地址：https://www.jetbrains.com/pycharm/download/other.html

全栈程序员-用户IM
2022年10月30日
一篇读懂无线充电技术（附方案选型及原理分析）「建议收藏」

一篇读懂无线充电技术（附方案选型及原理分析）「建议收藏」一文读懂无线充电技术（附方案选型及原理分析）0.背景1.无线供电特点2.无线供电原理及实现方式3.现有解决方案分析4.FAQ及相关测试5.参考资料0.背景现今几乎所有的电子设备，如手机，MP3和笔记本电脑等，进行充电的方式主要是有线电能传输，既一端连接交流电源,另一端连接便携式电子设备充电电池的。这种方式有很多不利的地方，首先频繁的插拔很容易损坏主板接口，另外不…

全栈程序员-用户IM
2022年5月7日
解决github下载慢及–recursive慢的问题（亲测好用）[通俗易懂]

在gitclone的地址，例如https://github.com/pytorch/pytorch，改为https://gitclone.com/github.com/pytorch/pytorch，也即加上前缀gitclone.com，然后就可以愉快的下载了(亲测有效)。对于子模块，可以先不要在gitclone的时候加上–recursive，等主体部分下载完之后，该文件夹中有个隐藏文件称为：.gitmodules，把子项目中的url地址同样加上gitclone.com前缀，然后利用gits..

全栈程序员-用户IM
2022年4月12日
PyCharm使用教程 — 7、使用PyCharm进行DeBug调试

PyCharm使用教程 — 7、使用PyCharm进行DeBug调试DeBug运行/调试Bug大家都知道是程序中的错误，导致程序不能正常运行。而DeBug的字面意思就是解决Bug。DeBug执行的方式也是有三种，与上面的代码运行章节类似，1、右键DeBug2、导航栏DeBug点击导航栏绿色的蜘蛛图标即可DeBug启动。3、通过mainDebug执行如果程序有main函数入口，可以点击左侧的绿色小三角，然后选择上图标识的Debug项目名即可。4、断点如果Debug的程序没有断点，则跟正常的执行没有区别。断点：一个断点标注一个代码行，当程序执行到

全栈程序员-用户IM
2022年8月25日

发表回复

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