hdu 1757 A Simple Math Problem （矩阵快速幂）

Description

Lele now is thinking about a simple function f(x).

If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .

Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.

Input

The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.

Output

For each case, output f(k) % m in one line.

Sample Input

10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0

Sample Output

45
104


这就算我写的第一道矩阵快速幂的题了！
矩阵快速幂的给我的感觉就是先找规律，YY出一个n*n的矩阵，矩阵左边写一列数，矩阵右边写一列数。让矩阵乘上右边那一列数等于左边的那列数。盗张图！！

然后......然后就没有然后了QWQ，输出答案就行了。
代码如下：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int N=10;
 5 int k,m;
 6 struct Matrix//用结构体来存矩阵
 7 {
 8     long long int mat[N][N];//直接上long long int 别找事
 9 }matrix;
10 void init()
11 {
12     for (int i=0;i<N;++i)
13     scanf("%lld",&matrix.mat[0][i]);
14     for (int i=1;i<N;++i)
15     {
16         for (int j=0;j<N;++j)
17         {
18             if (i==j+1)
19             matrix.mat[i][j]=1;
20             else
21             matrix.mat[i][j]=0;
22         }
23     }
24 }
25 Matrix operator * (Matrix a,Matrix b)//定义乘号
26 {
27     Matrix c;
28     for (int i=0;i<N;++i)
29     {
30         for (int j=0;j<N;++j)
31         {
32             c.mat[i][j]=0;//初始化值为0
33             for (int k=0;k<N;++k)
34             c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
35             c.mat[i][j]%=m;//记得取模，否则就炸了
36         }
37     }
38     return c;
39 }
40 Matrix Pow (int n)//定义快速幂函数
41 {
42     Matrix t;
43     if (n==1)
44     return matrix;
45     if (n&1)
46     return matrix*Pow(n-1);
47     else
48     {
49         Matrix temp=Pow(n>>1);
50         return temp*temp;
51     }
52 }
53 int main()
54 {
55     //freopen("de.txt","r",stdin);
56     while (~scanf("%d%d",&k,&m))
57     {
58         init();
59         if (k<10)
60         {
61             printf("%lld
",matrix.mat[0][k]%m);
62             continue;
63         }
64         Matrix temp=Pow(k-9);
65         long long int ans=0;
66         for (int i=0;i<N;++i)
67         {
68             ans += temp.mat[0][i]*(N-i-1);
69             ans%=m;
70         }
71         printf("%lld
",ans);
72     }
73     return 0;
74 }