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;
}

补充：软件开发 , C++ ,