求助,WA+TLE
查看原帖
求助,WA+TLE
72118
AThousandSuns楼主2018/8/9 12:58

标准矩乘+费马,但是WA+TLE,n,m109n,m\geq 10^9 的点都炸了。初步判断是输入的问题。但就是找不出来啊……

#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]);
}
2018/8/9 12:58
加载中...