A Simple Math Problem

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 4 Accepted Submission(s) : 2

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

Author

linle

Source

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

 1 #include<cstdio>
 2 #include<cstring>
 3 const int N=10;
 4 using namespace std;
 5 int k,m;
 6 
 7 struct Matrix
 8 {
 9     int map[N][N];
10 };
11 
12 Matrix matrix;
13 
14 void init()
15 {
16      for(int i=0;i<N;i++)
17      {
18          scanf("%d",&matrix.map[0][i]);
19      }
20      for(int i=1;i<N;i++)
21      {
22          for(int j=0;j<N;j++)
23          {
24              if(i==(j+1))matrix.map[i][j]=1;
25              else matrix.map[i][j]=0;
26          }
27      }
28 }
29 
30 Matrix mul(Matrix a,Matrix b)
31 {
32      Matrix c;
33      for(int i=0;i<N;i++)
34     {
35          for(int j=0;j<N;j++)
36         {
37              c.map[i][j]=0;
38              for(int k=0;k<N;k++)
39              {
40                  c.map[i][j]+=a.map[i][k]*b.map[k][j];
41              }
42              c.map[i][j]%=m;
43          }
44      }
45      return c;
46  }
47 
48  Matrix quickpow(int k)
49  {
50      if(k==1)  return matrix;
51      if(k&1) return mul(matrix,quickpow(k-1));
52      else
53      {
54          Matrix temp=quickpow(k>>1);
55          return mul(temp,temp);
56      }
57  }
58 
59  int main()
60  {
61      while(scanf("%d%d",&k,&m)!=EOF)
62      {
63          init();
64          if(k<10)
65          {
66              printf("%d\n",k%m);
67              continue;
68          }
69          Matrix temp=quickpow(k-9);
70          int ans=0;
71          for(int i=0;i<N;i++)
72          {
73              ans+=temp.map[0][i]*(N-i-1);
74              ans%=m;
75          }
76          printf("%d\n",ans);
77      }
78      return 0;
79  }