记录编号	584997	评测结果	AAAAAAAAAA
题目名称	[POJ 5015]233矩阵	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-11-17 21:01:21	内存使用	0.00 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 13,mod = 10000007;
typedef long long ll;
ll n,m;
struct Matrix{
    ll a[N][N],n,m;
    void clear(){
        n = m = 0;
        memset(a,0,sizeof(a));
    }
    Matrix operator * (const Matrix &x)const{
        Matrix y;y.clear();
        y.n = n;y.m = m;
        for(int i = 1;i <= n;i++) 
            for(int j = 1;j <= m;j++)
                for(int k = 1;k <= m;k++)
                    y.a[i][j] = (y.a[i][j] + (a[i][k] * x.a[k][j]) % mod) % mod;
        return y;
    } 
}c,f;
int main(){
    freopen("233matrix.in","r",stdin);
    freopen("233matrix.out","w",stdout);
    while(cin>>n>>m){
        c.clear();f.clear();
        f.n = 1,f.m = n+2;
        for(int i = 1;i <= n;i++)
            scanf("%lld",&f.a[1][i]);
        f.a[1][n+1] = 233,f.a[1][n+2] = 1;
        c.n = c.m = n+2;
        for(int i = 1;i <= n;i++){
            c.a[n+1][i] = 1;
            for(int j = 1;j <= i;j++)c.a[j][i] = 1;
        }
        c.a[n+1][n+1] = 10,c.a[n+2][n+1] = 3,c.a[n+2][n+2] = 1;
        while(m){
            if(m & 1)f = f * c;
            c = c * c;
            m >>= 1;
        }
        printf("%lld\n",f.a[1][n]);
    }
    
    return 0;
    
}