快速幂、矩阵快速幂
一、快速幂：
ll mypow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
二、矩阵快速幂：
#include<cstring>
#define ll long long
const int maxn=12;
struct Ma
{
ll m[maxn][maxn];
};
Ma mul(Ma a,Ma b,int n)
{
Ma temp;
memset(&temp,0,sizeof(temp));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
temp.m[i][j]+=a.m[i][k]*b.m[k][j];
return temp;
}
Ma mypow(Ma res,int N,int n)
{
Ma ans;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) ans.m[i][j]=1;
else ans.m[i][j]=0;
while(N)
{
if(N&1) ans=mul(ans,res,n);
res=mul(res,res,n);
N>>=1;
}
return ans;
}
