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

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

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？

如何安装Java？在本文中，我们将研究如何安装Java，在Windows操作系统中安装Java，如何检查已安装的版本以及设置环境变量。因此，让我们开始吧。如何安装Java？Java支持许多平台，例如Windows，Linux，Solaris等。这些平台具有自己的安装方法。在本教程中，我们将介绍32位和64位OS的安装过程Windows操作系统。Windows操作系统中的Java安装在Windows操作系统中，32位和64位Windows操作系统都具有类似的Java安装方式。主要区别在于它们的安装软件包。如何检查主机

全栈程序员-站长
2022年7月9日
20
python易错盲点排查之+=与+的区别分析以及一些赋值运算踩过的坑[通俗易懂]

python易错盲点排查之+=与+的区别分析以及一些赋值运算踩过的坑

全栈程序员-站长
2022年3月13日
35
对于梯度消失和梯度爆炸的理解

对于梯度消失和梯度爆炸的理解

全栈程序员-站长
2021年11月20日
58
Android滑动解锁功能实现,Android_滑动解锁

Android滑动解锁功能实现,Android_滑动解锁1.滑动解锁代码流程图：流程图图片资源：https://pan.baidu.com/s/1tkcw0tdxV78mnwHqOtcAGg提取码：2xsq2.代码：xml文件：xmlns:app=”http://schemas.android.com/apk/res-auto”xmlns:tools=”http://schemas.android.com/tools”android:layout_wi…

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

CompareNoCaseCString::CompareNoCaseintCompareNoCase(LPCTSTRlpsz)const;返回值：如果字符串是一样的（不区分大小写）则返回零值；如果CString对象

全栈程序员-站长
2022年7月4日
20
5G/NR SSB学习总结[通俗易懂]

5G/NR SSB学习总结[通俗易懂]6.1SSB概念同步信号和PBCH块(SynchronizationSignalandPBCHblock,简称SSB)，它由主同步信号(PrimarySynchronizationSignals,简称PSS)、辅同步信号(SecondarySynchronizationSignals,简称SSS)、PBCH三部分共同组成。6.2SSB特征…

全栈程序员-站长
2022年6月30日
33

发表回复

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