矩阵快速幂

矩阵快速幂

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll n,k;
struct rce{
    ll m[109][109];//矩阵 
    rce(){memset(m,0,sizeof(m));}
};
rce init(){
    rce temp;
    for(int i=0;i<=n;i++)    temp.m[i][i]=1;
    return temp;//初始化单位矩阵 
}
rce operator*(rce a,rce b)
{
    rce ans;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            ans.m[i][j]=0;
            for(int k=1;k<=n;k++)
                ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod;
        }   
    }
    return ans; 
}
rce powrce(rce a,ll n)
{
    rce temp=init();
    while(n)
    {
        if(n&1)     temp=temp*a;
        a=a*a;
        n>>=1;    
    }
    return temp;    
} 
int main()
{
    //注意时刻开longlong和求模 
}