hdu-5015 233 Matrix 矩阵快速幂

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

这题一开始就想到用矩阵快速幂做，不过思路跑歪了，想着从a[n,m]去逆推出a[0,0~m]每一位的倍数关系啥的。发现比较难求解而且233正向递推好写，反向涉及除法就很难写了。

其实没有那么复杂，我们把a[1~n,0]以及下一列的第一位，以及3这个数构造成矩阵，那么对于a[i][j]就可以用之前的矩阵通过矩阵乘法求出了。

#include <iostream>
#include <cstring>
#define LL long long
using namespace std;
const LL mod=10000007;
int mx[105][105];
struct mmx
{
    LL n,m;
    LL c[12][12];//需要根据题目开大
    void initMath(LL _n)//初始化方阵
    {
        m=n=_n;
    }
    void initOne(LL _n)//初始化单位矩阵
    {
        m=n=_n;
        for(LL i=0; i<n; i++)
            for(LL j=0; j<m; j++)
                c[i][j]=(i==j);
    }
    void print()//测试打印
    {
        for(LL i=0; i<n; i++)
        {
            for(LL j=0; j<m; j++)
                cout<<c[i][j]<<' ';
            cout<<endl;
        }
    }
};
mmx Mut(mmx a,mmx b)
{
    mmx c;
    c.n=a.n,c.m=b.m;
    for(LL i=0;i<a.n;i++)
        for(LL j=0;j<b.m;j++)
        {
            LL sum=0;
            for(LL k=0;k<b.n;k++)
                sum+=a.c[i][k]*b.c[k][j],sum%=mod;
            c.c[i][j]=sum;
        }
    return c;
}
mmx fastMi(mmx a,LL b)
{
    mmx mut;mut.initOne(a.n);
    while(b)
    {
        if(b%2!=0)
            mut=Mut(mut,a);
        a=Mut(a,a);
        b/=2;
    }
    return mut;
}
int main()
{
    cin.sync_with_stdio(false);
    LL n,m;
    while(cin>>n>>m)
    {
        n+=2;
        mmx src;
        src.n=1,src.m=n;
        for(int i=1; i<n-1; i++)
            cin>>src.c[0][i];
        src.c[0][0]=233;
        src.c[0][n-1]=3;
        mmx cal;
        cal.initOne(n);
        for(int i=0; i<n+2; i++)
        {
            if(i==0)cal.c[i][0]=10,cal.c[i][n-1]=0;
            else if(i==n-1)cal.c[i][0]=1,cal.c[i][n-1]=1;
            else cal.c[i][0]=0,cal.c[i][n-1]=0;
            for(int j=1;j<n-1;j++)
            {
                if(i==0)cal.c[i][j]=1;
                else if(i==n-1) cal.c[i][j]=0;
                else
                {
                    if(i<=j)cal.c[i][j]=1;
                    else cal.c[i][j]=0;
                }
            }
        }
        //cal.print();
        mmx ans=Mut(src,fastMi(cal,m));

        cout<<ans.c[0][n-2]<<endl;
    }
    return 0;
}