今天带大家推一个简单的矩阵快速幂?教大家推比fbi难一点的矩阵...
首先看a[i][j]=a[i-1][j]+a[i][j-1].其中n行(n<=10)m列(m<=1e9).我们可以观察到n很小对吧.
这个题目是已知矩阵第一行的所有数都长23、233、2333这样.矩阵的第一列已经给出,那么就是看我们如何用第一列推出第m列了?(因为n很大,不可能用n推矩阵.)
好了,我们继续观察递推公式,a[i][j]=a[i-1][j]+a[i][j-1].我们很容易知道,a[i][j]=a[i][0]+a[1~i][j-1].
如此,我们就很容易推出矩阵了.

f[i]={a1,0,a2,0,…,an,0 };
f[i]=f[i-1]*G；
G={
10 10 10 ... 10 10
0   1  1 ...
0   0  1 ...
...
1 1 1  ... 1 1
}

代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e7+7;
int n,m;
ll G[12][12];
ll f[12];
void mul1()
{
    ll g[12];
    for(int k=0;k<=n+1;k++) g[k]=f[k];
    memset(f,0,sizeof f);
    for(int i=0;i<=n+1;i++)
    {
        for(int j=0;j<=n+1;j++)
        {
            f[i]=(f[i]+G[j][i]*g[j])%mod;
        }
    }
}

void mul2()
{
    ll G1[12][12],G2[12][12];
    for(int i=0;i<=n+1;i++)
    {
        for(int j=0;j<=n+1;j++)
        {
            G1[i][j]=G2[i][j]=G[i][j]; 
        }
    }
    memset(G,0,sizeof G);
    for(int i=0;i<=n+1;i++)
    {
        for(int j=0;j<=n+1;j++)
        {
            for(int k=0;k<=n+1;k++)
            {
                G[i][j]=(G[i][j]+G1[i][k]*G2[k][j])%mod;
            }
        }
    }
}

void get_ans()
{
    while(m)
    {
        if(m&1) mul1();
        mul2();
        m>>=1;
    }
}

int main()
{
    while(cin>>n>>m)
    {
        memset(G,0,sizeof G);
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                G[i][j]=1;
            }
        }
        for(int i=0;i<=n;i++)   G[0][i]=10;
        for(int i=0;i<=n+1;i++) G[n+1][i]=1;
        f[0]=23;f[n+1]=3;
        for(int i=1;i<=n;i++) cin>>f[i];
        get_ans();
        cout<<f[n]<<endl;
    }
    return 0;
}