模板题
定义$lfloor x floor$表示小于等于$x$的最大整数，$lceil x ceil$表示大于等于$x$的最小整数
不难发现，若$ain Z^{+}$且$b,xin Z$，则$axle biff xle lfloorfrac{b}{a} floor$、$axge biff xge lfloorfrac{b-1}{a} floor+1$
通过拉格朗日插值法，预处理出$S_{k}(n)=sum_{i=0}^{n}i^{k}$（定义$0^{0}=1$）关于$n$的$k+1$次多项式，并记其中的$i$次项系数为$S_{k}[i]$，即有$S_{k}(n)=sum_{i=0}^{k+1}S_{k}[i]cdot n^{i}$
记$F_{k_{1},k_{2}}(n,a,b,c)=sum_{x=0}^{n}x^{k_{1}}lfloorfrac{ax+b}{c} floor^{k_{2}}$，问题即求该式$F_{k_{1},k_{2}}(n,a,b,c)$
对其分类讨论：
1.若$n<0$，那么原式即为0
2.若$a
otin [0,c)$，不妨假设$a=ic+a'$（其中$iin Z$且$a'in [0,c)$），那么原式即
$$
egin{array}{ll}F_{k_{1},k_{2}}(n,a,b,c)
&=sum_{x=0}^{n}x^{k_{1}}(lfloorfrac{a'x+b}{c}
floor+ix)^{k_{2}}\
&=sum_{x=0}^{n}x^{k_{1}}sum_{k=0}^{k_{2}}{k_{2}choose k}lfloorfrac{a'x+b}{c}
floor^{k}(ix)^{k2-k}\
&=sum_{k=0}^{k_{2}}{k2choose k}i^{k_{2}-k}F_{k_{1}+k_{2}-k,k}(n,a',b,c)end{array}
$$
3.若$b
otin [0,c)$，不妨假设$b=ic+b'$（其中$iin Z$且$b'in [0,c)$），那么原式即
$$
egin{array}{ll}F_{k_{1},k_{2}}(n,a,b,c)
&=sum_{x=0}^{n}x^{k_{1}}(lfloorfrac{ax+b'}{c}
floor+i)^{k_{2}}\
&=sum_{x=0}^{n}x^{k_{1}}sum_{k=0}^{k_{2}}{k_{2}choose k}lfloorfrac{ax+b'}{c}
floor^{k}i^{k2-k}\
&=sum_{k=0}^{k_{2}}{k2choose k}i^{k_{2}-k}F_{k_{1},k}(n,a,b',c)end{array}
$$
4.不为以上几种情况，先处理$k_{2}=0$的部分，即$F_{k_{1},0}(n,a,b,c)=sum_{x=0}^{n}x^{k_{1}}=S_{k_{1}}(n)$
接下来，若$a=0$则其余部分均为0，否则原式即
$$
egin{array}{ll}F_{k_{1},k_{2}}(n,a,b,c)
&=sum_{x=0}^{n}x^{k_{1}}sum_{i=0}^{lfloorfrac{ax+b}{c}
floor-1}left((i+1)^{k_{2}}-i^{k_{2}}
ight)\
&=sum_{x=0}^{n}x^{k_{1}}sum_{i=0}^{lfloorfrac{ax+b}{c}
floor-1}sum_{k=0}^{k_{2}-1}{k_{2}choose k}i^{k}\
&=sum_{k=0}^{k_{2}-1}{k_{2}choose k}sum_{i=0}^{lfloorfrac{an+b}{c}
floor-1}i^{k}sum_{x=lfloorfrac{ic+c-b-1}{a}
floor+1}^{n}x^{k_{1}}\
&=sum_{k=0}^{k_{2}-1}{k_{2}choose k}sum_{i=0}^{lfloorfrac{an+b}{c}
floor-1}i^{k}left(S_{k_{1}}(n)-S_{k_{1}}(lfloorfrac{ic+c-b-1}{a}
floor)
ight)\
&=C-sum_{k=0}^{k_{2}-1}{k_{2}choose k}sum_{i=0}^{lfloorfrac{an+b}{c}
floor-1}i^{k}sum_{k'=0}^{k_{1}+1}S_{k_{1}}[k']cdot lfloorfrac{ic+c-b-1}{a}
floor^{k'}\
&=C-sum_{k=0}^{k_{2}-1}{k_{2}choose k}sum_{k'=0}^{k_{1}+1}S_{k_{1}}[k']cdot F_{k,k'}(lfloorfrac{an+b}{c}
floor-1,c,c-b-1,a)end{array}
$$
其中$k_{2}>0$，$C$为$S_{k_{1}}(n)$对应的部分，即
$$
C=sum_{k=0}^{k_{2}-1}{k_{2}choose k}S_{k}(lfloorfrac{an+b}{c}
floor-1)S_{k_{1}}(n)
$$
考虑递归计算，即对于状态$(n,a,b,c)$求出所有$k_{1},k_{2}in N^{*}$的$F_{k_{1},k_{2}}(n,a,b,c)$，注意到转移的$k_{1}+k_{2}$单调不增，因此只需要考虑$k_{1}+k_{2}le K=10$的状态即可
由此，递归状态内的计算复杂度为$o(K^{4})$，而状态中的$a$和$c$即为辗转相除，即递归层数为$o(log n)$
综上，时间复杂度为$o(tK^{4}log n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 15 4 #define K 10 5 #define mod 1000000007 6 #define ll long long 7 struct Data{ 8 int a[N][N]; 9 Data(){ 10 memset(a,0,sizeof(a)); 11 } 12 }; 13 int t,n,a,b,c,k1,k2,inv[N],C[N][N],mi[N],g[N],S[N][N]; 14 void init(){ 15 inv[0]=inv[1]=1; 16 for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod; 17 for(int i=0;i<N;i++){ 18 C[i][0]=C[i][i]=1; 19 for(int j=1;j<i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; 20 } 21 for(int i=0;i<N;i++)mi[i]=1; 22 for(int i=0;i<=K;i++){ 23 int s=0; 24 for(int j=0;j<=i+1;j++){ 25 s=(s+mi[j])%mod; 26 int sum=s; 27 memset(g,0,sizeof(g)); 28 g[0]=1; 29 for(int k=0;k<=i+1;k++) 30 if (j!=k){ 31 sum=(ll)sum*inv[abs(j-k)]%mod; 32 if (j<k)sum=mod-sum; 33 for(int l=i+1;l;l--)g[l]=(g[l-1]-(ll)g[l]*k%mod+mod)%mod; 34 g[0]=mod-(ll)g[0]*k%mod; 35 } 36 for(int k=0;k<=i+1;k++)S[i][k]=(S[i][k]+(ll)sum*g[k])%mod; 37 } 38 for(int j=0;j<N;j++)mi[j]=(ll)mi[j]*j%mod; 39 } 40 } 41 int get_sum(int k,int n){ 42 int s=1,ans=0; 43 for(int i=0;i<=k+1;i++){ 44 ans=(ans+(ll)S[k][i]*s)%mod; 45 s=(ll)s*n%mod; 46 } 47 return ans; 48 } 49 Data dfs(int n,int a,int b,int c){ 50 Data ans; 51 if (n<0)return ans; 52 if (a>=c){ 53 Data s=dfs(n,a%c,b,c); 54 mi[0]=1; 55 for(int i=1;i<N;i++)mi[i]=(ll)mi[i-1]*(a/c)%mod; 56 for(int k1=0;k1<=K;k1++) 57 for(int k2=0;k1+k2<=K;k2++) 58 for(int k=0;k<=k2;k++)ans.a[k1][k2]=(ans.a[k1][k2]+(ll)C[k2][k]*mi[k2-k]%mod*s.a[k1+k2-k][k])%mod; 59 return ans; 60 } 61 if (b>=c){ 62 Data s=dfs(n,a,b%c,c); 63 mi[0]=1; 64 for(int i=1;i<N;i++)mi[i]=(ll)mi[i-1]*(b/c)%mod; 65 for(int k1=0;k1<=K;k1++) 66 for(int k2=0;k1+k2<=K;k2++) 67 for(int k=0;k<=k2;k++)ans.a[k1][k2]=(ans.a[k1][k2]+(ll)C[k2][k]*mi[k2-k]%mod*s.a[k1][k])%mod; 68 return ans; 69 } 70 for(int k1=0;k1<=K;k1++)ans.a[k1][0]=get_sum(k1,n); 71 if (!a)return ans; 72 int nn=((ll)a*n+b)/c; 73 Data s=dfs(nn-1,c,c-b-1,a); 74 for(int k1=0;k1<=K;k1++) 75 for(int k2=1;k1+k2<=K;k2++) 76 for(int k=0;k<k2;k++){ 77 int sum=0; 78 for(int kk=0;kk<=k1+1;kk++)sum=(sum+(ll)S[k1][kk]*s.a[k][kk])%mod; 79 sum=((ll)get_sum(k,nn-1)*ans.a[k1][0]-sum+mod)%mod; 80 sum=(ll)sum*C[k2][k]%mod; 81 ans.a[k1][k2]=(ans.a[k1][k2]+sum)%mod; 82 } 83 return ans; 84 } 85 int main(){ 86 init(); 87 scanf("%d",&t); 88 while (t--){ 89 scanf("%d%d%d%d%d%d",&n,&a,&b,&c,&k1,&k2); 90 printf("%d ",dfs(n,a,b,c).a[k1][k2]); 91 } 92 return 0; 93 }