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

全栈程序员-站长 • 2022年9月12日上午8:46 • 未分类 • 阅读 3

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

UDP协议详解[通俗易懂]

UDP协议详解[通俗易懂]目录1、简介2、UDP协议3、端口4、UDP和ARP之间的交互5、UDP适用场景6、UDP洪水1、简介UDP（UserDatagramProtocol）是一个简单的面向消息的传输层协议，尽管UDP提供标头和有效负载的完整性验证（通过校验和），但它不保证向上层协议提供消息传递，并且UDP层在发送后不会保留UDP消息的状态。因此，UDP有时被称为不可靠的数据报协议。如果需要传输可靠性，则必须在用户应用程序中实现。UDP使用具有最小协议机制的简单无连接通信模型。UDP提供数据

全栈程序员-站长
2022年6月7日
51
常用八大测试用例设计方法有哪些_测试用例编写方法

常用八大测试用例设计方法有哪些_测试用例编写方法1、等价类划分（EquivalancePartitioning）测试的思想：将程序的输入域划分为若干个区域（等价类），并在每个等价类中选择一个具有代表性的元素生成测试用例。该方法是常用的黑盒（BlackboxTesting）测试用例（Testcase）设计方法。等价类划分可有两种不同的情况:有效等价类和无效等价类。有效等价类是指对于程序的规格说明来说是合理的、有意义的输入数据构成的集合，它能检验程序是否可以实现规格说明中所规定的功能需求。无效等价类是指对程序的规格说明是不合理的或无意义的输入数据所

全栈程序员-站长
2022年10月12日
0
matlab 画折线图

matlab 画折线图代码：效果图：x=1:1:5就是x轴上的数据，从1开始到5结束（即应该有五个数据），每个数据的间隔是1.把开始的1改成2，结束的5改成6，整个折线图就会向右平移一个单位。plot（x,a,’-*b’,x,b,’-or’）是设置折线图中相应点和线的特征的，函数说明如下：对于‘’内的线条形状，总结了如下图：线型：线条宽度：指定线条的宽度，取值为整数（…

全栈程序员-站长
2022年4月29日
42
YUI3 入门

YUI3 入门YUI3入门，算是自己学习YUI3的GettingStarted.

全栈程序员-站长
2022年7月12日
14
elastic search数据库集群部署「建议收藏」

elastic search数据库集群部署「建议收藏」ES数据库安装elasticasearchelasticsearch的概念：是一个实时的分布式搜索和分析引擎，它可以用于全文搜索，结构化搜索以及分析。它是一个建立在全文搜索引擎ApacheLucene基础上的搜索引擎，使用Java语言编写。1、elasticsearch和MongoDB/redis/memcache一样，是非关系性数据库是一个接近实时的搜索平台，从所索引这个文档到能够被搜索到只有一个轻微的延迟，企业应用定位：采用restfullapi标准的可扩展和高可用的实时数据分析

全栈程序员-站长
2022年6月9日
43
RDN怎么配置环境

RDN怎么配置环境非root怎么安装linux版本的lua和torchhttps://blog.csdn.net/BRAVE_NO1/article/details/90260800

全栈程序员-站长
2022年6月18日
29

发表回复

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