hdu 1757 A Simple Math Problem

A Simple Math Problem

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4038 Accepted Submission(s): 2437

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

104

Author

linle

Source

2007省赛集训队练习赛（6）_linle专场

Recommend

lcy | We have carefully selected several similar problems for you: 1575 1588 3117 2276 2256

典型的矩阵快速幂问题，第一次写，参考了别人的代码，感觉收益良多，最重要的地方在于构建一个矩阵。

借用一下别人代码的推论：

下面我们研究一下这道题如何运用矩阵。

f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10)
构造的矩阵是:

|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；

题意：按照题目给的公式，求f(k) % m的值。

附上代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 struct mat
 6 {
 7     int m[10][10];
 8 };
 9 int mod;
10 
11 mat mul(mat a,mat b)
12 {
13     mat c;
14     int i,j,k;
15     memset(c.m,0,sizeof(c.m));
16     for(i=0; i<10; i++)
17         for(j=0; j<10; j++)
18         {
19             for(k=0; k<10; k++)
20             {
21                 c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod;
22             }
23             c.m[i][j]%=mod;
24         }
25     return c;
26 }
27 
28 mat product(mat a,int k)
29 {
30     if(k==1) return a;
31     else if(k&1)
32         return mul(product(a,k-1),a);
33     else
34         return product(mul(a,a),k/2);
35 }
36 
37 int main()
38 {
39     int i,j,k;
40     mat a;
41     while(~scanf("%d%d",&k,&mod))
42     {
43         for(i=9; i>=0; i--)
44             scanf("%d",&a.m[9][i]);
45         if(k<10)
46         {
47             printf("%d
",k%mod);
48             continue;
49         }
50         for(i=0; i<9; i++)
51             for(j=0; j<10; j++)
52                 if(j==i+1) a.m[i][j]=1;
53                 else a.m[i][j]=0;
54         mat b=product(a,k-9);
55         int ans=0;
56         for(i=0; i<10; i++)
57             ans+=(b.m[9][i]*i)%mod;
58         printf("%d
",ans%mod);
59     }
60     return 0;
61 }