233 Matrix

链接：http://acm.hdu.edu.cn/showproblem.php?pid=5015
思路：
我们可以考虑将每个列向量组看成由前一个列向量组通过线性变换得到的。矩阵快速幂的核心思想就是构造关系矩阵，即考虑当前列向量组如何由之前向量组左乘一个矩阵得到。那么考察某一列与之前一列的关系，我们发现，首先233到2333的关系是23310+3，即a0i=a0i-110+3,能够显然发现我们通过10和a01,a02,a03,a04...a0n是构造不出来这个关系的，那么我们就把这个n*n矩阵给拓展一下，多一个维度，最后加个3。然后列向量最后加个1，然后为了使得这一变换的初始能够变换过来，应该对第一列做点手脚，让a00从0变到23，所有列向量最后都加一个维度，并赋值为1。
得到的关系矩阵为：

10 0 0 ... 0 3
10 1 0 ... 0 3
10 1 1 ... 0 3
...
10 1 1 ... 1 3
0  0 0 ... 0 1

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 10000007;

int arr[15];
int n, m;


struct Matrix{
    ll m[15][15];

    Matrix(){
//        memset(m,0,sizeof(m));
//        for(int i=0;i<=n+1;i++){
//            m[i][n+1]=1;
//            if(i==n+1) continue;
//            m[i][0]=10;
//            for(int j=1;j<=i;j++)
//                m[i][j]=1;
//        }
        memset(m ,0, sizeof(m));
        for(int i = 0; i <= n+1; i++){
            if(i == n+1) {
                m[i][n+1] = 1;
                continue;
            }
            m[i][n+1] = 3;
            m[i][0] = 10;
            for(int j = 1; j <= i; j++){
                m[i][j] = 1;
            }
        }
    }

    void clear(){
        memset(m,0,sizeof(m));
        for(int i=0;i<=n+1;i++)
            m[i][i]=1;
    }

    void display(){
        cout<<"Matrix's begin:"<<endl;
        for(int i=0;i<=n+1;i++)
            for(int j=0;j<=n+1;j++)
                if(j<n+1) cout<<m[i][j]<<" ";
                else cout<<m[i][j]<<endl;
        cout<<"Matrix's end:"<<endl;
    }

    friend Matrix operator*(Matrix a,Matrix b){
        Matrix ans;
        for(int i=0;i<=n+1;i++)
            for(int j=0;j<=n+1;j++){
                ans.m[i][j]=0;
                for(int k=0;k<=n+1;k++)
                    ans.m[i][j]+=a.m[i][k]*b.m[k][j]%mod;
            }
        return ans;
    }

    friend Matrix operator^(Matrix base,ll k){
        Matrix ans;
        ans.clear();
        while(k){
            if(k&1) ans=ans*base;
            base=base*base;
            k>>=1;
        }
        return ans;
    }

};

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        arr[0] = 23, arr[n+1] = 1;
        for(int i = 1; i <= n; i++){
            cin >> arr[i];
        }        
        Matrix base;
        base = base^m;

        ll ans = 0;
        for(int i = 0; i <= n+1; i++){
            ans = (ans + 1ll*base.m[n][i]*arr[i] % mod )%mod;
        }
        cout << ans << endl;
    }
}