点击这里查看原题
这个题需要一步一步推算:
f[1][1]=1 f[1][m]=a ^ (m-1) * f[1][1]+b * (a ^ (n-1)-1) / (a-1) f[2][1]=f[1][m] * c+d=c * a^(m-1) * f[1][1]+b * c * (a ^ (n-1)-1) / (a-1) + d
设e=a ^ (m-1) * c,g=b * c * (a ^ (m-1)-1) / (a-1) + d，则：
f[n+1][1]=e ^ n * f[1][1] + g * (e ^ n-1) / (e-1)
此外因为n,m都很大，因此还要用到费马小定理：a^(p-1)%p=1，也就是说需要让n,m分别对 ( p-1 ) 取模，然后进行快速幂运算。 最后我们只需要算出f[n+1][1]然后减d乘c的逆元即可。 注意long long，不然会出现各种奇怪错误。
/* User:Small Language:C++ Problem No.:3240 */ #include<bits/stdc++.h> #define ll long long #define inf 999999999 using namespace std; const int M=1000005; const ll mod=1e9+7; char x[M],y[M]; ll a,b,c,d,p; struct no{ ll uni,ord; }n,m; void calmod(char *s,no &a){ int len=strlen(s); a.uni=a.ord=0; for(int i=0;i<len;i++){ a.uni=(a.uni*10+s[i]-'0')%mod; a.ord=(a.ord*10+s[i]-'0')%(mod-1); } } ll pow(ll a,ll b){ ll res=1; while(b){ if(b&1LL) res=res*a%mod; a=a*a%mod; b=b/2LL; } return res; } ll ni(ll x){ return pow(x,mod-2); } int main(){ freopen("data.in","r",stdin);// scanf("%s%s%lld%lld%lld%lld",x,y,&a,&b,&c,&d); calmod(x,n); calmod(y,m); if(a==1){ b=(b*c%mod*(m.uni-1)+d)%mod; a=c; } else{ ll k=b*ni(a-1)%mod,t=pow(a,m.ord-1); a=t*c%mod; b=(k*(t-1)%mod*c+d)%mod; } if(a==1){ p=(1+n.uni*b)%mod; } else{ ll k=b*ni(a-1)%mod,t=pow(a,n.ord); p=(t+(t-1)*k)%mod; } printf("%lld\n",((p-d)*ni(c)%mod+mod)%mod); return 0; }