Bzoj 3240
据学长的话来说
这是当年noi最简单的一道题
于是抱着试一试的心态做了一做 蒟蒻QAQ如何实现？
(fx+k)=a(fx−1+k)
展开就可以得到一个等比数列； 然后根据等比数列的性质可得： 
fx=ax−1∗f1+b∗(ax−1−1)/(a−1)
至此我们完成了将每行的最后一个用第一个表示
再根据第三个条件，同理可得：
fi+1=am−1∗c∗fi+b∗c∗(am−1−1)/(a−1)+d
这里我们可以得到每一列的第i个如何用第i-1表示；
那么再将这个公式的系数看成一个整体，又是一个等比数列
直接再用第一个公式算出f(n,m);
f(n,m
注意事项
因为主人公婷婷是十分残暴的，数据范围很扎心；
那么我们知道
am=ammodφ(p)
所以在读入的时候我们需要处理一对用于乘法的n,m和一对用于幂的n,m；
φ(mod)=mod−1
最后再啰嗦一句，就是逆元处理
#include#include #include #include #define LL long long #define mod 1000000007using namespace std;struct node{ LL mul,pow;}n,m;LL a,b,c,d,aa,bb,ans;LL xx,yy;void read(node &x){ char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch<='9'&&ch>='0'){ x.mul=(x.mul*10+ch-'0')%mod; x.pow=(x.pow*10+ch-'0')%(mod-1); ch=getchar(); }}LL ksm(LL x,LL y){ LL rtn=1; while(y){ if(y&1)rtn=(rtn*x)%mod; x=(x*x)%mod; y>>=1; } return rtn; }void getinv(LL a,LL b){ if(!b){xx=1,yy=0;return;} getinv(b,a%b); LL tmp=xx; xx=yy; yy=tmp-(a/b)*yy;}int main(){#ifdef YSW freopen("In.txt","r",stdin);#endif read(n);read(m); scanf("%d%d%d%d",&a,&b,&c,&d); aa=a,bb=b; if(a==1){ a=c; b=((m.mul-1)*b%mod*c%mod+d)%mod; } else{ getinv(a-1,mod); LL k=(b*(xx%mod+mod)%mod)%mod; LL t=ksm(a,(m.pow-1+mod-1)%(mod-1)); a=t*c%mod; b=(k*(t-1)%mod*c%mod+d)%mod; } if(a==1){ a=1; b=b*(n.mul-1)%mod; } else{ getinv(a-1,mod); LL k=(b*(xx+mod)%mod)%mod; LL t=ksm(a,(n.pow-1+mod-1)%(mod-1)); a=t; b=k*(t-1)%mod; } LL f1=(a+b)%mod; if(aa==1){ ans=(f1+(m.mul-1)*bb%mod)%mod; } else{ getinv(aa-1,mod); LL k=(bb*(xx+mod)%mod)%mod; LL t=ksm(aa,(m.pow-1+mod-1)%(mod-1)); aa=t; bb=k*(t-1)%mod; LL tmp=aa*f1%mod; ans=(tmp+bb)%mod; } printf("%lld",ans); return 0; }