HDU 1757 A Simple Math Problem

http://acm.hdu.edu.cn/showproblem.php?pid=1757

还是矩阵+快速幂，注意要把初值乘回去并且注意方向

#include <iostream>
using namespace std ;
void mul(int a[11][11],int b[11][11],int n)
{
    int c[11][11] ;
    int i,j,k ;
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
            c[i][j]=0 ;
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
            for(k=0;k<10;k++)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%n ;
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
            a[i][j]=c[i][j] ;
}
void qpow(int m[11][11],__int64 k,int n)
{
    int ans[11][11] ;
    int buff[11][11] ;
    int i,j ;
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
            if(i==j)
                ans[i][j]=1 ;
            else
                ans[i][j]=0 ;
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
            buff[i][j]=m[i][j] ;
    while(k)
    {
        if(k&1)
            mul(ans,buff,n) ;
        mul(buff,buff,n) ;
        k>>=1 ;
    }
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
            m[i][j]=ans[i][j] ;
}
int main()
{
    __int64 k ;
    int m ;
    int a[11],p[11][11] ;
    while(~scanf("%I64d%d",&k,&m))
    {
        for(int i=0;i<10;i++)
            scanf("%d",&a[i]) ;
        if(k<10)
        {
            printf("%d\n",k%m) ;
            continue ;
        }
        for(int i=0;i<10;i++)
            p[i][0]=a[i] ;
        for(int i=0;i<10;i++)
            for(int j=1;j<10;j++)
                if(j-i==1)
                    p[i][j]=1 ;
                else
                    p[i][j]=0 ;
        qpow(p,k-9,m) ;
        int ans=0 ;
        for(int i=0;i<10;i++)
            ans=(ans+p[i][0]*(9-i))%m ;
        printf("%d\n",ans) ;
    }
    return 0 ;
}