学步园

推的时候注意a_0 到 a_9的顺序!

#include <stdio.h>
#include <string.h>
#define ff(i,n) for(int i=0;i<n;i++)

int M;

struct Mat
{
    int m[10][10];
    friend Mat operator*(Mat a,Mat b)
    {
        Mat c;
        memset(c.m,0,sizeof(c.m));
        ff(i,10)
        ff(j,10)
        ff(k,10)
        {
            c.m[i][j]+=((long long)(a.m[i][k]%M)*(b.m[k][j]%M))%M;
            c.m[i][j]%=M;
        }
        return c;
    }
}A,I;

void DEBUG(Mat a)
{
    ff(i,10)
    {
        ff(j,10)
            printf("%d\t",a.m[i][j]);
        puts("");
    }
    puts("");
}

Mat Power(Mat a,int n)
{
    Mat t=I;
    for(;n;n>>=1)
    {
        if(n&1)
            t=t*a;
        a=a*a;
    }
    return t;
}

int main()
{
    //freopen("hdu1754in","r",stdin);
    memset(A.m,0,sizeof(A.m));
    memset(I.m,0,sizeof(I.m));
    ff(i,10)
    {
        if(i)
            A.m[i-1][i]=1;
        I.m[i][i]=1;
    }


    int x;
    while(scanf("%d%d",&x,&M)==2)
    {
        Mat a=A;
        ff(i,10)
            scanf("%d",&a.m[9][9-i]);
        if(x<10)
        {
            printf("%d\n",x);
            continue;
        }
        a=Power(a,x);

        int sum=0;
        ff(i,10)
            sum+=(long long)(a.m[0][i]%M)*(i%M),sum%=M;
        printf("%d\n",sum);
    }
}