OI練習題 式子 recursion

【問題描述】

動態規劃 DP 的實現形式之一是遞推，因此遞推在 oi 中十分重要。在某資訊學的分支學科中， LC 學會瞭如何求一階線性遞推數列。由於他現在正在學習主幹學科，因此希望知道求出 N 階線性遞推數列。為此，他瞭解到了以下的內容：

一個 N 階線性遞推式是這樣的式子：

也就是說，這個數列的每一項都是由他之前連續 N 項加權相加所得。其中還包括一個常數 an 。

例如，當 N=2 ， a0=a1=1 ， a2=0 時，這個式子就是我們熟悉的斐波那契數列。當然，作為這界條件， f0 、 f1…f n-1 都是已知的。

LC 對這如何去求這個式子一籌莫展，因此請你來幫助他。你的任務就是對於一個給定的 N 階線性遞推式，求出它的第 K 項是多少。

【輸入文件】

第一行兩個整數： N ， K ，其中 N 表示這個式子是 N 階線性遞推式， K 表示你需要求得那一項。

第二行有 N+1 個整數： A0,A1,… ， An ，表示這個遞推式的係數。

第三行有 N 個整數： F0 ， F1 ， …. ， Fn-1 ，表示數列的初始值。

【輸出文件】

只有一行，其中只有一個整數，表示這個數列第 K 項的值。由於資料較大，你只需輸出結果 mod 9973 的值。

 

【樣例輸入】

2 10

1 1 0

0 1

【樣例輸出】

55

【資料範圍】

對於 50% 的資料： N<=K<=10^6

對於 100% 的資料：

1<N<10

N<=K<=101^8

1<=Ai ， Fi<=10^4

【提示】

矩陣(Matrix)是一個n*m（n行m列）的數組。例如[0 1]就是一個1*2的矩陣。

矩陣乘法這樣定義：

如果A是n*m的矩陣，B是m*t的矩陣，設矩陣C=A*B，則Cij=∑Aik*Bkj，其中C是一個n*t的矩陣。

例如，對於斐波那契數可以列出這個遞推公式：

矩陣乘法滿足結合率，但不滿足交換率

【分析】

矩陣乘法。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25687

01 #include <cstdio>
02 #include <cstdlib>
03 #include <iostream>
04 using namespace std;
05 const int MOD=9973;
06 const int MAXN=12;
07 class Matrix
08 {
09 public:
10     int m[MAXN][MAXN];
11 };
12 Matrix A,B;
13
14 unsigned long long  N,K;
15 void init()
16 {
17     scanf("%d",&N);
18     cin>>K;
19     for(int i=2;i<=N;i++) A.m[i][i-1]=1;
20     int x;
21     for(int i=1;i<=N+1;i++)
22     {
23         scanf("%d",&x);
24         A.m[i][N]=x;
25     }
26     A.m[N+1][N+1]=1;
27 }
28
29 Matrix multiply(Matrix M,Matrix P)
30 {
31     Matrix T;
32     for(int i=1;i<=N+1;i++)
33         for(int j=1;j<=N+1;j++)
34                 T.m[i][j]=0;
35     for(int i=1;i<=N+1;i++)
36         for(int j=1;j<=N+1;j++)
37             for(int k=1;k<=N+1;k++)
38                 T.m[i][j]=(T.m[i][j]+M.m[i][k]*P.m[k][j])%MOD;
39     return T;
40 }
41
42 Matrix pow(unsigned long long k)
43 {
44     Matrix T;
45     if(k==1) {return A;}
46     T=pow(k/2);
47     T=multiply(T,T);
48     if(k%2==1) {T=multiply(T,A);}
49     return T;
50 }
51
52 int main()
53 {
54     freopen("recursion.in","r",stdin);
55     freopen("recursion.out","w",stdout);
56     init();
57     B=pow(K);
58     int Ans=B.m[N+1][1];
59     int x;
60     for(int i=1;i<=N;i++)
61     {
62         scanf("%d\n",&x);
63         Ans=(Ans+B.m[i][1]*x)%MOD;
64     }
65     printf("%d\n",Ans%MOD);
66     return 0;
67 }