一波化式子，$f[1][m]=a^{m-1}+b\sum_{i=0}^{m-2}a^i$，用快速幂+逆元求等比数列可以做到$logm$
设$v=a^{m-1},k=\sum_{i=0}^{m-2}a^i$
那么$f[1][m]=v+bk$
再对纵列化一波式子，$f[i][m]=f[i-1][m]*vc+bk+vd$
如果你直接上个矩乘可以拿到65的好分数
#include<iostream>
#include<cstdio>
#include<cstring>
#define ri register int
using namespace std;
typedef long long ll;
const ll P=1e9+;
const ll W=1e9;
char q[];
struct bnum{
ll a[],len;
bnum(){memset(a,,sizeof(a));len=;}
void init(){
scanf("%s",q); int z=; len=;
for(ri i=strlen(q)-;i>=;--i){
a[len]+=(q[i]-)*z; z*=;
if(z==W) z=,++len;
}
while(!a[len]&&len) --len;
}
ll mod(){
ll re=;
for(ri i=;i<=len;++i) re=(re*W+a[i])%P;
return re;
}
void rem1(){
--a[];
for(ri i=;a[i]<;++i) a[i]+=W,--a[i+];
while(!a[len]&&len) --len;
}
bnum div2(){
bnum c; c.len=len; ll x=;
for(ri i=len;i;--i)
x=x*W+a[i],c.a[i]=x/,x%=;
while(!c.a[c.len]&&c.len) --c.len;
return c;
}
}n,m;
struct mat{
ll a[][];
mat(){memset(a,,sizeof(a));}
mat operator * (const mat &b) const{
mat c;
for(ri i=;i<;++i)
for(ri j=;j<;++j)
for(ri k=;k<;++k)
c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%P)%P;
return c;
}
}s,p;
ll Pow(ll x,ll y){
ll re=;
for(;y;y>>=,x=x*x%P) if(y&) re=re*x%P;
return re;
}
ll Pow_b(ll x,bnum y){
ll re=;
for(;y.len;y=y.div2(),x=x*x%P) if(y.a[]&) re=re*x%P;
return re;
}
mat Pow_m(mat x,bnum y){
mat re; for(ri i=;i<;++i) re.a[i][i]=;
for(;y.len;y=y.div2(),x=x*x) if(y.a[]&) re=re*x;
return re;
}
int main(){
ll a,b,c,d,v,k;
n.init(); m.init(); n.rem1(); m.rem1();
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
v=Pow_b(a,m);
if(a>) k=(v-+P)%P*Pow((a-+P)%P,P-)%P;
else k=m.mod();
s.a[][]=(b*k+v)%P; s.a[][]=(b*k%P+v*d%P)%P;
p.a[][]=v*c%P; p.a[][]=p.a[][]=;
p=Pow_m(p,n); s=s*p;
printf("%lld",s.a[][]);
return ;
}
65pts
观察发现，这个矩乘可以再化：
$f[n][m]=(v+bk)(vc)^{n-1}+(bk+vd)\sum_{i=0}^{n-2}(vc)^i$
观察这个式子，复杂度主要在快速幂上，复杂度$O(logn+logm)$
考虑缩小$n,m$
假设存在：$a^n=a^{n-x}\, mod \; p$，$p$为质数
$\therefore a^x=1\, mod \; p$
根据费马小定理，$x=p-1$
$\therefore a^n=a^{n\, mod\, p-1}\, mod \; p$
输入$n,m$时记下它们$mod\, p,p-1$的值，代入式子即可
注意等比数列公比$=1$时需要特判
#include<iostream>
#include<cstdio>
#include<cstring>
#define ri register int
using namespace std;
typedef long long ll;
const ll P=1e9+;
ll a,b,c,d,v,k,n,m,_n,_m,a_,k_,v_;
void init(){
char c=getchar();
while(c<''||c>'') c=getchar();
while(''<=c&&c<=''){
n=(n*+c-)%P;
_n=(_n*+c-)%(P-);
c=getchar();
}c=getchar();
while(c<''||c>'') c=getchar();
while(''<=c&&c<=''){
m=(m*+c-)%P;
_m=(_m*+c-)%(P-);
c=getchar();
}
}
ll Pow(ll x,ll y){
ll re=;
for(;y;y>>=,x=x*x%P) if(y&) re=re*x%P;
return re;
}
int main(){
init(); scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
n=(n-+P)%P; _n=(_n-+P-)%(P-);
m=(m-+P)%P; _m=(_m-+P-)%(P-);
v=Pow(a,_m);
k=a>?(v-+P)*Pow(a-+P,P-)%P:m;
a_=v*c%P; v_=Pow(a_,_n);
k_=a_>?(v_-+P)*Pow(a_-+P,P-)%P:n;
printf("%lld",((v+b*k)%P*v_%P+(b*k+v*d)%P*k_%P)%P);
return ;
}