A Simple Math Problem

10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0

45
104

题解及代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=1e9;
struct mat
{
    __int64 t[10][10];
    void set()
    {
        memset(t,0,sizeof(t));
    }
} a,b,c;

mat multiple(mat a,mat b,int n,int p)
{
    int i,j,k;
    mat temp;
    temp.set();
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
        {
            if(a.t[i][j]!=0)
                for(k=0; k<n; k++)
                    temp.t[i][k]=(temp.t[i][k]+a.t[i][j]*b.t[j][k]+p)%p;
        }
    return temp;
}

mat quick_mod(mat b,int n,int m,int p)
{
    mat t;
    t.set();
    for(int i=0;i<n;i++) t.t[i][i]=1;
    while(m)
    {
        if(m&1)
        {
            t=multiple(t,b,n,p);
        }
        m>>=1;
        b=multiple(b,b,n,p);
    }
    return t;
}

void init(int a[])
{
   b.set();
   for(int i=0;i<10;i++)
   {
       for(int j=0;j<10;j++)
       if(j==9)
       b.t[i][j]=a[i];
       else if(i==j+1) b.t[i][j]=1;
   }
   /*for(int i=0;i<=9;i++)
   {
       for(int j=0;j<=9;j++)
        cout<<b.t[i][j]<<" ";
       puts("");
   }
   */
}

int main()
{
    int  k,M;
    int  s[10];
    while(cin>>k>>M)
    {
        for(int i=9;i>=0;i--)
            cin>>s[i];
        if(k<10)
        {
            cout<<k%M<<endl;
            continue;
        }
        init(s);
        a=quick_mod(b,10,k,M);
        __int64 ans=0;

        for(int i=0;i<=9;i++)
        {
            ans=(ans+i*a.t[i][0])%M;
        }
        cout<<ans<<endl;
    }
    return 0;
}
/*
简单的矩阵快速幂，上面的代码可以用地做模版，
当然inin()除外，init()用来所有矩阵的初始化。
这道题关键就是矩阵的构造了：
令矩阵a=|0 1 2 3 4 5 6 7 8 9|
矩阵b是转换矩阵，下面：
|0 0 0 0 0 0 0 0 0 a[9]|
|1 0 0 0 0 0 0 0 0 a[8]|
|0 1 0 0 0 0 0 0 0 a[7]|
|0 0 1 0 0 0 0 0 0 a[6]|
|0 0 0 1 0 0 0 0 0 a[5]|
|0 0 0 0 1 0 0 0 0 a[4]|
|0 0 0 0 0 1 0 0 0 a[3]|
|0 0 0 0 0 0 1 0 0 a[2]|
|0 0 0 0 0 0 0 1 0 a[1]|
|0 0 0 0 0 0 0 0 1 a[0]|
其余就是套模版就行了。
*/

hdu 1757 A Simple Math Problem（矩阵快速幂）,布布扣,bubuko.com

hdu 1757 A Simple Math Problem（矩阵快速幂）

原文：http://blog.csdn.net/knight_kaka/article/details/38184617