题目名称 642. 线性递推式
输入输出 recursion.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2012-02-17
开放分组 全部用户
提交状态
分类标签
二分法 矩阵运算
通过:40, 提交:107, 通过率:37.38%
Gravatardestiny 100 0.000 s C++
GravatarRespawn 100 0.000 s C++
GravatarHzoi_chairman 100 0.000 s C++
Gravatar金身人面兽 100 0.000 s C++
GravatarTBK 100 0.004 s C++
Gravatar王者自由 100 0.004 s C++
Gravatarkaaala 100 0.004 s C++
Gravatardevil 100 0.004 s C++
Gravatarthomount 100 0.005 s C++
GravatarMakazeu 100 0.006 s C++
关于 线性递推式 的讨论
kai!
GravatarMakazeu
2012-07-30 10:28 1楼
此题和1493题类似
本题的真实数据范围是:N<=10,k在long long范围内
题上那个公式代码太高端了不敢动……
Gravatarcstdio
2014-01-23 16:53 2楼
这机智。。

Gravatar落尘
2015-07-11 10:55 3楼
Gravatarcsbrother
2017-10-26 22:07 4楼

642. 线性递推式

★★   输入文件:recursion.in   输出文件:recursion.out   简单对比
时间限制:1 s   内存限制:128 MB
【问题描述】
动态规划 DP 的实现形式之一是递推,因此递推在 OI 中十分重要。在某信息学的分支学科中, LC 学会了如何求一阶线性递推数列。由于他现在正在学习主干学科,因此希望知道求出 $N$ 阶线性递推数列。为此,他了解到了以下的内容:
一个 $N$ 阶线性递推式是这样的式子:
\[ f_i=a_0f_{i-n}+a_1f_{i-(n-1)}+\cdots+a_{n-1}f_{i-1}+a_n \]
也就是说,这个数列的每一项都是由他之前连续 $N$ 项加权相加所得。其中还包括一个常数 $a_n$ 。
例如,当 $N=2$, $a_0=a_1=1$, $a_2=0$ 时,这个式子就是我们熟悉的斐波那契数列。当然,作为这界条件, $f_0, f_1,...,f_{n-1}$ 都是已知的。
LC 对这如何去求这个式子一筹莫展,因此请你来帮助他。你的任务就是对于一个给定的 $N$ 阶线性递推式,求出它的第 $K$ 项是多少。
【输入文件】
第一行两个整数: $N$ , $K$ ,其中 $N$ 表示这个式子是 $N$ 阶线性递推式, $K$ 表示你需要求得那一项。
第二行有 $N+1$ 个整数: $A_0, A_1,…, A_n$ ,表示这个递推式的系数。
第三行有 $N$ 个整数: $F_0, F_1, ...,  F_{n-1}$ ,表示数列的初始值。
【输出文件】
只有一行,其中只有一个整数,表示这个数列第 $K$ 项的值。由于数据较大,你只需输出结果$\mod 9973$的值。
【样例输入】
2 10
1 1 0
0 1
【样例输出】
55
【数据范围】
对于 50% 的数据: $N \le K\le 10^6$
对于 100% 的数据:
 $N\le K\le 10^8$
$1\le A_i , F_i\le 10^4$
【提示】
矩阵($Matrix$)是一个$n·m$($n$行$m$列)的数组。例如[0 1]就是一个$1·2$的矩阵。
矩阵乘法这样定义:
    如果$\boldsymbol{A}=n\times m$,$\boldsymbol{B}=m\times t$,设矩阵$\boldsymbol{C}=\boldsymbol{A}\times\boldsymbol{B}$,则$c_{i,j}=\sum a_{i,k}\cdot b_{k,j}$,其中$\boldsymbol{C}=n\times t$。
例如,对于斐波那契数可以列出这个递推公式:

\[ [f_i\quad f_{i+1}] = [f_{i-1}\quad f_i] \times \left[\begin{array}{cc} 0 & 1 \\ 1 & 1\end{array}\right] \]