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

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

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

http://blog.csdn.net/sio__five/article/details/37072641

题目大意

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 .
现在给你k和m，求f(k) % m。

解题思路：

f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10)

其中k为10^9数量级，必然不能用递推的方式做。这类题目可以通过构造矩阵，用矩阵快速幂来做。

构造的矩阵是:

|0 1 0 ......... 0|    |f0|   |f1 |
|0 0 1 0 ....... 0|    |f1|   |f2 |
|................1| *  |..| = |...|
|a9 a8 .........a0|    |f9|   |f10|

我们看到规律了，每次要到下次个A*B，以此类推则由A*A*A.......A*B；

1. const int maxn = 20;  
2. const int maxm = 20;  
3. ll mod, k;  
4. struct Matrix {  
5.     int n, m;  
6.     int a[maxn][maxm];  
7.     void clear() {  
8.         n = m = 0;  
9.         memset(a, 0, sizeof(a));  
10.     }  
11.     Matrix operator * (const Matrix &b) const { //实现矩阵乘法  
12.         Matrix tmp;  
13.         tmp.clear();  
14.         tmp.n = n; tmp.m = b.m;  
15.         for (int i = 0; i < n; i++)  
16.             for (int j = 0; j < b.m; j++)  
17.                 for (int k = 0; k < m; k++) {  
18.                     tmp.a[i][j] += a[i][k] * b.a[k][j];  
19.                     tmp.a[i][j] %= mod;  
20.                 }  
21.         return tmp;  
22.     }  
23. };  
24. Matrix A, B;  
25. void init() {  
26.     A.clear(); //矩阵A是构造的矩阵  
27.     A.n = A.m = 10;  
28.     for (int i = 0; i < 9; i++)  
29.         A.a[i][i + 1] = 1;  
30.     B.clear();  
31.     B.n = 10; B.m = 1; //矩阵B是f(x)的前10个数  
32.     for (int i = 0; i < 10; i++)  
33.         B.a[i][0] = i;  
34. }  
35. Matrix Matrix_pow(Matrix A, ll k, ll mod) { //矩阵快速幂  
36.     Matrix res;  
37.     res.clear();  
38.     res.n = res.m = 10;  
39.     for (int i = 0; i < 10; i++) res.a[i][i] = 1;  
40.     while(k) {  
41.         if (k & 1) res = A * res;  
42.         k >>= 1;  
43.         A = A * A;  
44.     }  
45.     return res;  
46. }  
47. int main () {  
48.     init();  
49.     while(cin>>k>>mod) {  
50.         int x;  
51.         for (int i = 0; i < 10; i++) {  
52.             scanf("%d", &x);  
53.             A.a[9][9 - i] = x;  
54.         }  
55.         if (k < 10) {  
56.             printf("%lld\n", k % mod);  
57.         }  
58.         else {  
59.             Matrix res = Matrix_pow(A, k - 9, mod);  
60.             res = res * B;  
61.             cout<<res.a[9][0]<<endl;  
62.         }  
63.     }  
64.     return 0;  
65. }  

Also check http://www.acmerblog.com/hdu-1757-A-Simple-Math-Problem-2734.html

51	int main(){

52	while(scanf("%d%d",&k,&m)!=EOF){

53	Initiate();

54

if(k<10){

55	printf("%d\n",k%m);

56

continue;

57

}

58	Matrix temp=Pow(k-9);

59	int ans=0;

60	for(int i=0;i<N;i++){

61	ans+=temp.map[0][i]*(N-i-1); //最后要乘上f[9],f[8],...,f[1],f[0];

62

ans%=m;

63

}

64	printf("%d\n",ans);

65

}

66

return 0;

67

}

附上一链接：http://blog.csdn.net/q3498233/article/details/5786180
Also check http://blog.csdn.net/u010709592/article/details/30144433
Read full article from Problem - 1757