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

矩陣快速冪的應用，還不怎么會用。。。
代碼如下：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int k,m; struct Maxtri {int r,c;int a[15][15]; }; Maxtri ori,res; void init() {memset(res.a,0,sizeof(res.a));for(int i=1;i<=10;i++)res.a[i][i]=1;for(int i=2;i<=10;i++)for(int j=1;j<=10;j++){if(i-1!=j)ori.a[i][j]=0;elseori.a[i][j]=1;} } Maxtri maxtri(Maxtri x,Maxtri y) {Maxtri z;memset(z.a,0,sizeof(z.a));for(int i=1;i<=10;i++){for(int k=1;k<=10;k++){if(x.a[i][k]==0) continue;for(int j=1;j<=10;j++)z.a[i][j]=(z.a[i][j]+(x.a[i][k]*y.a[k][j])%m)%m;//這一點取模一定要注意，錯了n遍 }}return z; } void maxtri_mod(int n) {while(n){if(n%2!=0)res=maxtri(res,ori);ori=maxtri(ori,ori);n/=2;} } int main() {while(scanf("%d%d",&k,&m)!=EOF){for(int i=1;i<=10;i++)scanf("%d",&ori.a[1][i]);init();if(k<=9){printf("%d\n",k%m);continue;}maxtri_mod(k-9);int sum=0;for(int i=1;i<=10;i++){sum+=(res.a[1][i]*(10-i))%m;sum%=m;}printf("%d\n",sum%m);}return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的A Simple Math Problem（矩阵快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。