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

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1757

思路：直接递推肯定超时，比赛的时候就想着找规律，如何把递推式转化为f1到f9的和规律，想炸了，没想到时矩阵快速幂，能把时间压为log(n)，不会超时，代码也很好写

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>
const int inf = 0x3f3f3f3f;//1061109567
typedef long long ll;
const int maxn = 40000;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int mod;
using namespace std;
struct node
{
    int a[10][10];
};
node matrixmul(node a,node b)
{
    node c;
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            c.a[i][j] = 0;
            for(int k=0; k<10; k++)
            {
                c.a[i][j] += a.a[i][k] * b.a[k][j];
                c.a[i][j] %= mod;
            }
        }
    }
    return c;
}
node quickmod(node s,int k)
{
    node ans;
    memset(ans.a,0,sizeof(s.a));
    for(int i=0; i<10; i++)
        ans.a[i][i] = 1;
    while(k)
    {
        if(k & 1)
            ans = matrixmul(ans,s);
        k = k >> 1;
        s = matrixmul(s,s);
    }
    return ans;
}
int main()
{
    int b[10];
    int k;
    while(scanf("%d%d",&k,&mod) != EOF)
    {
        node sa,sb;
        for(int i=0; i<10; i++)
            scanf("%d",&b[i]);
        memset(sa.a,0,sizeof(sa.a));
        for(int i=0; i<10; i++)
        {
            if(i == 0)
            {
                for(int j=0; j<10; j++)
                   sa.a[i][j] = b[j];
            }
            else
            {
                sa.a[i][i-1] = 1;
            }
        }
        sa = quickmod(sa,k-9);//左边的矩阵初始化
        memset(sb.a,0,sizeof(sb.a));
        for(int i=0; i<=9; i++)
        {
            sb.a[i][0] = 9 - i;
        }
        sb = matrixmul(sa,sb);//右边的矩阵初始化
        printf("%d\n",sb.a[0][0]%mod);
    }
    return 0;
}