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

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

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

使用Java中间MessageDigest该文本MD5加密（Java中间MD5样品加密算法演示）

使用Java中间MessageDigest该文本MD5加密（Java中间MD5样品加密算法演示）

全栈程序员-站长
2022年1月9日
48
云服务器和云虚拟主机的区别、利弊[通俗易懂]

云服务器和云虚拟主机的区别、利弊[通俗易懂]虚拟主机虚拟主机是利用云技术把一台服务器划分为多个的“虚拟的主机”，划分出来的虚拟主机具有独立域名（能够独立的搭建网站）和完整的Internet服务器的功能，但是带宽和IP是共享服务器的。优势：由于是分享的服务器带宽、IP等所有在价格上分成便宜。虚拟主机一般都是配置好环境的用户能直接使用，客户在购买使用上非常方便。劣势：由于带宽时共享的，虚拟主机的带宽上是没有保障的。IP共享那么安全性…

全栈程序员-站长
2022年6月25日
28
activity 工作流程引擎-如何画流程图

activity 工作流程引擎-如何画流程图前言:activity工作流引擎是当前最流行的工作流,最近公司一直在用这个感觉还是很好用的，学习过程中也有不少的坑所以简单记录一下相关知识的学习过程吧如何画流程图，这里使用浏览器端的一个工具和eclipse里面操作都差不多吧1.流程图里面的节点，如开始，子流程等都是通过拖拽的方式加载的2.一个节点通过点击即可选择下一个节点事件3.如果一个节点出现分支，或者判断的情况可以在流程线上设置…

全栈程序员-站长
2022年7月27日
27
冲刺阶段 – PMP易错概念（持续更新中）

冲刺阶段 – PMP易错概念（持续更新中）文章目录1.基础概念2.整合管理3.范围管理4.进度管理5.成本管理6.质量管理7.资源管理8.沟通管理9.风险管理10.采购管理11.相关方管理1.基础概念1.“管理层在项目管理方面缺乏经验”不是项目失败的原因。管理层可以不懂项目管理，但项目经理必须要非常精通项目管理，这里还有一个假设就是组织拥有非常充分的组织过程资产，即便经验不足，也可以去学习和借鉴组织过程资产。2.子项目的划分，根据项目的复杂性来划分，以便更好的去管理与控制项目，子项目会细化工作，故增加工

全栈程序员-站长
2022年5月19日
42
贪心 Codeforces Round #263 (Div. 2) C. Appleman and Toastman

贪心 Codeforces Round #263 (Div. 2) C. Appleman and Toastman

全栈程序员-站长
2021年9月8日
59
pycharm怎么安装requests模块_python3安装模块

pycharm怎么安装requests模块_python3安装模块问题引入：今天在学习Python网络请求的时候，导入requests模块时一直报红色波浪线，如图：反复折腾，一直以为自己没有安装requests模块，反复安装反复卸载：安装方法：首先cd进入C:\Python27\Scripts 执行pipinstallrequests命令可以自动安装卸载方法：首先cd进入C:\Python27\Scripts 执行pipuninstallr…

全栈程序员-站长
2022年8月26日
11

发表回复

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