将线性递推式转化成矩阵乘法，再结合快速幂实现O(logn)

此法可广泛用于动态规划等递推题目

实现时仅需将*重载，其余同快速幂

#include
     
      #include
      
       using namespace std;#define ll long longconst ll p=1e9+7;ll n,k;struct Z{    ll a[105][105];    Z operator * (const Z &w) const //第一个const表示不改变w 第二个不改变a &表示不复制w     {        Z re;        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)                re.a[i][j]=0;        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)                for(int k=1;k<=n;k++)                    re.a[i][k]+=a[i][j]*w.a[j][k],                    re.a[i][k]=re.a[i][k]%p;        return re;    }};Z s,e;void Read(ll &x);void Write(ll x);Z power(Z w,ll kk){    Z re=e;    while(kk>0)    {        if(kk&1) re=re*w;        w=w*w;        kk>>=1;    }    return re;}int main(){    Read(n),Read(k);    for(int i=1;i<=n;i++)         for(int j=1;j<=n;j++)            Read(s.a[i][j]),e.a[i][j]=0;    for(int i=1;i<=n;i++) e.a[i][i]=1;    Z w=power(s,k);    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++) Write(w.a[i][j]%p),putchar(' ');        putchar('\n');    }    return 0;}void Read(ll &x){    ll i=1;    x=0;    char c=getchar();    while(c<'0' or c>'9')    {        if(c=='-') i=-1;        c=getchar();    }    while(c>='0' and c<='9')    {        x=x*10+(c-'0');        c=getchar();    }    x*=i;}void Write(ll x){    if(x<0)     {        putchar('-');        x=-1*x;    }    if(x>9) Write(x/10);    putchar(x%10+'0');}