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

程序员必备的6个辅助开发的软件神器有哪些_程序员最喜欢的五大神器

程序员必备的6个辅助开发的软件神器有哪些_程序员最喜欢的五大神器前言（欢迎评论区列出你认为牛逼的开发神器~）本文来自MeloDev的投稿，他的博客地址：http://www.jianshu.com/u/f5909165c1e8程序员必备简捷开发辅助工具总结写在前面：工欲善其事必先利其器，拥有简捷的开发辅助工具能大大提高我们程序猿的开发效率。Melo刚到学校就给大家总结了一些常用的辅助开发的工具，希望大家能喜欢，闲话不多说，马…

全栈程序员-站长
2022年10月19日
1
hi3516dv300 sdk_Hi3516DV300

hi3516dv300 sdk_Hi3516DV300Ｈi3516DV300编译环境搭建问题及解决1.安装完工具链，提示找不到gcc问题：bash:/opt/hisi-linux/x86-arm/arm-hisiv300-linux/target/bin/arm-hisiv300-linux-gcc:没有那个文件或目录。安装完工具链，提示找不到gcc，但实际gcc工具已经安装上是由于开发环境是32位的，而当前的ubuntu是64位的解…

全栈程序员-站长
2022年9月23日
0
c语言stat函数返回值,stat函数

c语言stat函数返回值,stat函数一.概述：表头文件:#include#include定义函数:intstat(constchar*file_name,structstat*buf);函数说明:通过文件名filename获取文件信息，并保存在buf所指的结构体stat中返回值:执行成功则返回0，失败返回-1，错误代码存于errno错误代码:ENOENT参数fil…

全栈程序员-站长
2022年8月21日
11
uint16_t转换成char_16bit转8bit

uint16_t转换成char_16bit转8bit简单来说，uint8_t/uint16_t/uint32_t/uint64_t这些数据类型都只是别名而来，具体如下：一、C语言数据基本类型在C语言中有6种基本数据类型：short、int、long、float、double、char1）整型：shortint、int、longint2）浮点型：float、double3）字符类型：char二、分析uint8_…

全栈程序员-站长
2022年9月7日
0
09年后的经典电影_2010年好看的电影有哪些

09年后的经典电影_2010年好看的电影有哪些哈哈，这是我个人觉的09年最好看的电影，如果大家有不同的声音，请补充……01、《新娘大战》(BrideWars)　　影片导演：加里．文尼克　　影片主演：安妮．海瑟薇、凯特．哈德森、布莱恩．格林伯格、斯蒂夫．哈维　　发行公司：20世纪福克斯　　北美首映：2009年1月9日　　期待指数：★★★★★★★☆☆☆7星　　作品简介：　　两个从…

全栈程序员-站长
2022年9月30日
0
特征融合 & FFM(Feature Fusion Module) 特征融合模块

特征融合 & FFM(Feature Fusion Module) 特征融合模块FFM(FeatureFusionModule)特征融合模块

全栈程序员-站长
2022年5月4日
262

发表回复

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