HDU 1757

[a9,a8,a7,…,a0]*
|f(0) 1 0 0,0,0,0,0,0,0|
|f(1) 0 1 0,0,0,0,0,0,0|
|f(2) 0 0 1,0,0,0,0,0,0|
|f(3) 0 0 0,1,0,0,0,0,0|
|f(4) 0 0 0,0,1,0,0,0,0|
|f(5) 0 0 0,0,0,1,0,0,0|
|f(6) 0 0 0,0,0,0,1,0,0|
|f(7) 0 0 0,0,0,0,0,1,0|
|f(8) 0 0 0,0,0,0,0,0,1|
|f(9) 0 0 0,0,0,0,0,0,0|
=[a10,a9,…,a1]
[cpp] 
#include <iostream> 
using namespace std; 
 
int f[10]={0,1,2,3,4,5,6,7,8,9}; 
int a[10]; 
int m; 
 
struct N 
{ 
    int ans[10][10]; 
}; 
 
N Get_ans(N a,N b) 
{ 
    N temp; 
    int i,j,k; 
    for (i=0;i<10;i++) 
    { 
        for (j=0;j<10;j++) 
        { 
            temp.ans[i][j]=0;//不要忘記 
            for (k=0;k<10;k++) 
            { 
                temp.ans[i][j]+=(a.ans[i][k]*b.ans[k][j])%m; 
                temp.ans[i][j]%=m; 
            } 
        } 
    } 
    return temp; 
} 
 
N run(N node,int n) 
{ 
    if(n==1) return node; 
    N rtemp=run(node,n/2); 
    if(n%2) return Get_ans(node,Get_ans(rtemp,rtemp)); 
    else return Get_ans(rtemp,rtemp); 
} 
 
int main() 
{ 
    N node; 
    int i,n; 
    memset(node.ans,0,sizeof(node.ans)); 
    for (i=0;i<9;i++) 
    { 
        node.ans[i][i+1]=1; 
    } 
    while(scanf("%d%d",&n,&m)!=EOF) 
    { 
        for(i=0;i<10;i++) 
        { 
            scanf("%d",&node.ans[i][0]);//構造矩陣 
        } 
        if(n<10)//小於10的情況 
        { 
            printf("%d\n",n%m); 
            continue; 
        } 
        N now=run(node,n-9);//node的n-9次 
        int ians=0;//最終結果 
        for (i=9;i>0;i--)//計算結果 
        { 
            ians+=i*now.ans[9-i][0]; 
            ians%=m; 
        } 
        printf("%d\n",ians); 
    } 
    return 0; 
}