模板题
定义$\lfloor x\rfloor$表示小于等于$x$的最大整数，$\lceil x\rceil$表示大于等于$x$的最小整数
不难发现，若$a\in Z^{+}$且$b,x\in Z$，则$ax\le b\iff x\le \lfloor\frac{b}{a}\rfloor$、$ax\ge b\iff x\ge \lfloor\frac{b-1}{a}\rfloor+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}}\lfloor\frac{ax+b}{c}\rfloor^{k_{2}}$，问题即求该式$F_{k_{1},k_{2}}(n,a,b,c)$
对其分类讨论：
1.若$n<0$，那么原式即为0
2.若$a\not\in [0,c)$，不妨假设$a=ic+a'$（其中$i\in Z$且$a'\in [0,c)$），那么原式即
$$
\begin{array}{ll}F_{k_{1},k_{2}}(n,a,b,c)
&=\sum_{x=0}^{n}x^{k_{1}}(\lfloor\frac{a'x+b}{c}\rfloor+ix)^{k_{2}}\\
&=\sum_{x=0}^{n}x^{k_{1}}\sum_{k=0}^{k_{2}}{k_{2}\choose k}\lfloor\frac{a'x+b}{c}\rfloor^{k}(ix)^{k2-k}\\
&=\sum_{k=0}^{k_{2}}{k2\choose k}i^{k_{2}-k}F_{k_{1}+k_{2}-k,k}(n,a',b,c)\end{array}
$$
3.若$b\not\in [0,c)$，不妨假设$b=ic+b'$（其中$i\in Z$且$b'\in [0,c)$），那么原式即
$$
\begin{array}{ll}F_{k_{1},k_{2}}(n,a,b,c)
&=\sum_{x=0}^{n}x^{k_{1}}(\lfloor\frac{ax+b'}{c}\rfloor+i)^{k_{2}}\\
&=\sum_{x=0}^{n}x^{k_{1}}\sum_{k=0}^{k_{2}}{k_{2}\choose k}\lfloor\frac{ax+b'}{c}\rfloor^{k}i^{k2-k}\\
&=\sum_{k=0}^{k_{2}}{k2\choose 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，否则原式即
$$
\begin{array}{ll}F_{k_{1},k_{2}}(n,a,b,c)
&=\sum_{x=0}^{n}x^{k_{1}}\sum_{i=0}^{\lfloor\frac{ax+b}{c}\rfloor-1}\left((i+1)^{k_{2}}-i^{k_{2}}\right)\\
&=\sum_{x=0}^{n}x^{k_{1}}\sum_{i=0}^{\lfloor\frac{ax+b}{c}\rfloor-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}^{\lfloor\frac{an+b}{c}\rfloor-1}i^{k}\sum_{x=\lfloor\frac{ic+c-b-1}{a}\rfloor+1}^{n}x^{k_{1}}\\
&=\sum_{k=0}^{k_{2}-1}{k_{2}\choose k}\sum_{i=0}^{\lfloor\frac{an+b}{c}\rfloor-1}i^{k}\left(S_{k_{1}}(n)-S_{k_{1}}(\lfloor\frac{ic+c-b-1}{a}\rfloor)\right)\\
&=C-\sum_{k=0}^{k_{2}-1}{k_{2}\choose k}\sum_{i=0}^{\lfloor\frac{an+b}{c}\rfloor-1}i^{k}\sum_{k'=0}^{k_{1}+1}S_{k_{1}}[k']\cdot \lfloor\frac{ic+c-b-1}{a}\rfloor^{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'}(\lfloor\frac{an+b}{c}\rfloor-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}(\lfloor\frac{an+b}{c}\rfloor-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\n",dfs(n,a,b,c).a[k1][k2]);
91 }
92 return 0;
93 }
View Code