标准矩乘+费马,但是WA+TLE,n,m≥109 的点都炸了。初步判断是输入的问题。但就是找不出来啊……
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
struct matrix{
int n,m,a[3][3];
matrix():n(0),m(0){
memset(a,0,sizeof(a));
}
matrix operator*(const matrix mat)const{
matrix ans;
ans.n=n;
ans.m=mat.m;
for(int i=1;i<=n;i++)
for(int j=1;j<=mat.m;j++)
for(int k=1;k<=m;k++) ans.a[i][j]=(ans.a[i][j]+1ll*a[i][k]*mat.a[k][j]%mod)%mod;
return ans;
}
matrix operator^(int b)const{
matrix fac=*this,ans;
ans.n=ans.m=n;
for(int i=1;i<=n;i++) ans.a[i][i]=1;
for(;b;b>>=1,fac=fac*fac) if(b&1) ans=ans*fac;
return ans;
}
}beg,tmp1,tmp2,tmp3,ans;
char nstr[1000100],mstr[1000100];
int nl,ml,nmod,mmod,n,m,a,b,c,d;
int main(){
scanf("%s%s%d%d%d%d",nstr,mstr,&a,&b,&c,&d);
nmod=mod-(a!=1);mmod=mod-(c!=1);
nl=strlen(nstr);ml=strlen(mstr);
for(int i=0;i<nl;i++) n=((n<<1ll)+(n<<3ll)+(nstr[i]^48))%nmod;
for(int i=0;i<ml;i++) m=((m<<1ll)+(m<<3ll)+(mstr[i]^48))%mmod;
if(!n) n=nmod;
if(!m) m=mmod;
beg.n=1;beg.m=2;
beg.a[1][1]=beg.a[1][2]=1;
tmp1.n=tmp1.m=2;
tmp1.a[1][1]=a;tmp1.a[1][2]=0;
tmp1.a[2][1]=b;tmp1.a[2][2]=1;
tmp2.n=tmp2.m=2;
tmp2.a[1][1]=c;tmp2.a[1][2]=0;
tmp2.a[2][1]=d;tmp2.a[2][2]=1;
tmp3=(tmp1^(m-1))*tmp2;
ans=beg*(tmp3^(n-1))*(tmp1^(m-1));
printf("%d\n",ans.a[1][1]);
}