【题目链接】

• 点击打开链接

【思路要点】

• 以下考虑实现函数f u n c ( N , a , b , c ) func(N,a,b,c) func(N,a,b,c) ，计算0 ≤ k 1 + k 2 ≤ 10 0\leq k_1+k_2\leq10 0≤k1?+k2?≤10 的情况下所求式子的值，即
  ∑ i = 0 N i k 1 ? a i + b c ? k 2 \sum_{i=0}^{N}i^{k_1}\lfloor\frac{ai+b}{c}\rfloor^{k_2} i=0∑N?ik1??cai+b??k2?
• 若a = 0 a=0 a=0 或? a N + b c ? = 0 \lfloor\frac{aN+b}{c}\rfloor=0 ?caN+b??=0 ，那么，? a i + b c ? \lfloor\frac{ai+b}{c}\rfloor ?cai+b?? 的取值始终相同，答案即为
  ? a N + b c ? ∑ i = 0 N i k 1 \lfloor\frac{aN+b}{c}\rfloor\sum_{i=0}^{N}i^{k_1} ?caN+b??i=0∑N?ik1?
  可以用插值解决。
• 若a ≥ c a\geq c a≥c ，则令q = ? a c ? , r = a ? q c q=\lfloor\frac{a}{c}\rfloor,r=a-qc q=?ca??,r=a?qc ，所求式子即为
  ∑ i = 0 N i k 1 ( q i + ? r i + b c ? ) k 2 = ∑ i = 0 N i k 1 ∑ j = 0 k 2 ( k 2 j ) ( q i ) j ? r i + b c ? k 2 ? j = ∑ j = 0 k 2 ( k 2 j ) q j ∑ i = 0 N i k 1 + j ? r i + b c ? k 2 ? j \sum_{i=0}^{N}i^{k_1}(qi+\lfloor\frac{ri+b}{c}\rfloor)^{k_2}\\=\sum_{i=0}^{N}i^{k_1}\sum_{j=0}^{k_2}\binom{k_2}{j}(qi)^j\lfloor\frac{ri+b}{c}\rfloor^{k_2-j}\\=\sum_{j=0}^{k_2}\binom{k_2}{j}q^j\sum_{i=0}^{N}i^{k_1+j}\lfloor\frac{ri+b}{c}\rfloor^{k_2-j} i=0∑N?ik1?(qi+?cri+b??)k2?=i=0∑N?ik1?j=0∑k2??(jk2??)(qi)j?cri+b??k2??j=j=0∑k2??(jk2??)qji=0∑N?ik1?+j?cri+b??k2??j
  递归计算f u n c ( N , r , b , c ) func(N,r,b,c) func(N,r,b,c) 即可。
• 若b ≥ c b\geq c b≥c ，则令q = ? b c ? , r = b ? q c q=\lfloor\frac{b}{c}\rfloor,r=b-qc q=?cb??,r=b?qc ，所求式子即为
  ∑ i = 0 N i k 1 ( q + ? a i + r c ? ) k 2 = ∑ i = 0 N i k 1 ∑ j = 0 k 2 ( k 2 j ) q j ? a i + r c ? k 2 ? j = ∑ j = 0 k 2 ( k 2 j ) q j ∑ i = 0 N i k 1 ? a i + r c ? k 2 ? j \sum_{i=0}^{N}i^{k_1}(q+\lfloor\frac{ai+r}{c}\rfloor)^{k_2}\\=\sum_{i=0}^{N}i^{k_1}\sum_{j=0}^{k_2}\binom{k_2}{j}q^j\lfloor\frac{ai+r}{c}\rfloor^{k_2-j}\\=\sum_{j=0}^{k_2}\binom{k_2}{j}q^j\sum_{i=0}^{N}i^{k_1}\lfloor\frac{ai+r}{c}\rfloor^{k_2-j} i=0∑N?ik1?(q+?cai+r??)k2?=i=0∑N?ik1?j=0∑k2??(jk2??)qj?cai+r??k2??j=j=0∑k2??(jk2??)qji=0∑N?ik1??cai+r??k2??j
  递归计算f u n c ( N , a , r , c ) func(N,a,r,c) func(N,a,r,c) 即可。
• 否则，即a < c , b < c , ? a N + b c ? > 0 a< c,b< c,\lfloor\frac{aN+b}{c}\rfloor> 0 a0 ，令M = ? a N + b c ? M=\lfloor\frac{aN+b}{c}\rfloor M=?caN+b?? 。
• 注意到? a i + b c ? k 2 \lfloor\frac{ai+b}{c}\rfloor^{k_2} ?cai+b??k2? 较难处理，需要将其变形，有
  ? a i + b c ? k 2 = ∑ j = 0 ? a i + b c ? ? 1 ( ( j + 1 ) k 2 ? j k 2 ) \lfloor\frac{ai+b}{c}\rfloor^{k_2}=\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}((j+1)^{k_2}-j^{k_2}) ?cai+b??k2?=j=0∑?cai+b???1?((j+1)k2??jk2?)
• 注意这里规定0 0 = 0 0^0=0 00=0 。
• 上述变换的好处是提供了交换求和顺序的可能，由此，原式可变为
  ∑ i = 0 N i k 1 ∑ j = 0 ? a i + b c ? ? 1 ( ( j + 1 ) k 2 ? j k 2 ) = ∑ j = 0 M ? 1 ( ( j + 1 ) k 2 ? j k 2 ) ∑ i = 0 N i k 1 [ ? a i + b c ? ≥ j + 1 ] = ∑ j = 0 M ? 1 ( ( j + 1 ) k 2 ? j k 2 ) ∑ i = 0 N i k 1 [ i > ? c j + c ? b ? 1 a ? ] = ∑ j = 0 M ? 1 ( ( j + 1 ) k 2 ? j k 2 ) ∑ i = 0 N i k 1 ? ∑ j = 0 M ? 1 ( ( j + 1 ) k 2 ? j k 2 ) ∑ i = 0 ? c j + c ? b ? 1 a ? i k 1 \sum_{i=0}^{N}i^{k_1}\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}((j+1)^{k_2}-j^{k_2})\\=\sum_{j=0}^{M-1}((j+1)^{k_2}-j^{k_2})\sum_{i=0}^{N}i^{k_1}[\lfloor\frac{ai+b}{c}\rfloor\geq j+1]\\=\sum_{j=0}^{M-1}((j+1)^{k_2}-j^{k_2})\sum_{i=0}^{N}i^{k_1}[i> \lfloor\frac{cj+c-b-1}{a}\rfloor]\\=\sum_{j=0}^{M-1}((j+1)^{k_2}-j^{k_2})\sum_{i=0}^{N}i^{k_1}-\sum_{j=0}^{M-1}((j+1)^{k_2}-j^{k_2})\sum_{i=0}^{\lfloor\frac{cj+c-b-1}{a}\rfloor}i^{k_1} i=0∑N?ik1?j=0∑?cai+b???1?((j+1)k2??jk2?)=j=0∑M?1?((j+1)k2??jk2?)i=0∑N?ik1?[?cai+b??≥j+1]=j=0∑M?1?((j+1)k2??jk2?)i=0∑N?ik1?[i>?acj+c?b?1??]=j=0∑M?1?((j+1)k2??jk2?)i=0∑N?ik1??j=0∑M?1?((j+1)k2??jk2?)i=0∑?acj+c?b?1???ik1?
• 靠前的求和符号可以直接计算，考虑靠后的求和符号。
• ( j + 1 ) k 2 ? j k 2 (j+1)^{k_2}-j^{k_2} (j+1)k2??jk2? 显然是关于j j j 的k 2 ? 1 k_2-1 k2??1 次多项式，而∑ i = 0 ? c j + c ? b ? 1 a ? i k 1 \sum_{i=0}^{\lfloor\frac{cj+c-b-1}{a}\rfloor}i^{k_1} ∑i=0?acj+c?b?1???ik1? 也是关于? c j + c ? b ? 1 a ? \lfloor\frac{cj+c-b-1}{a}\rfloor ?acj+c?b?1?? 的k 1 + 1 k_1+1 k1?+1 次多项式，不妨令为A ( x ) , B ( x ) A(x),B(x) A(x),B(x) 。
• 那么
  ∑ j = 0 M ? 1 ( ( j + 1 ) k 2 ? j k 2 ) ∑ i = 0 ? c j + c ? b ? 1 a ? i k 1 = ∑ i = 0 M ? 1 ∑ j = 0 k 2 ? 1 A i i j ∑ k = 0 k 1 + 1 B k ? c j + c ? b ? 1 a ? k = ∑ j = 0 k 2 ? 1 A i ∑ k = 0 k 1 + 1 B k ∑ i = 0 M ? 1 i j ? c j + c ? b ? 1 a ? k \sum_{j=0}^{M-1}((j+1)^{k_2}-j^{k_2})\sum_{i=0}^{\lfloor\frac{cj+c-b-1}{a}\rfloor}i^{k_1}\\=\sum_{i=0}^{M-1}\sum_{j=0}^{k_2-1}A_ii^j\sum_{k=0}^{k_1+1}B_k\lfloor\frac{cj+c-b-1}{a}\rfloor^{k}\\=\sum_{j=0}^{k_2-1}A_i\sum_{k=0}^{k_1+1}B_k\sum_{i=0}^{M-1}i^j\lfloor\frac{cj+c-b-1}{a}\rfloor^{k} j=0∑M?1?((j+1)k2??jk2?)i=0∑?acj+c?b?1???ik1?=i=0∑M?1?j=0∑k2??1?Ai?ijk=0∑k1?+1?Bk??acj+c?b?1??k=j=0∑k2??1?Ai?k=0∑k1?+1?Bk?i=0∑M?1?ij?acj+c?b?1??k
  递归计算f u n c ( M ? 1 , c , c ? b ? 1 , a ) func(M-1,c,c-b-1,a) func(M?1,c,c?b?1,a) 即可。
• 注意到在递归中( a , c ) → ( a % c , c ) → ( c , a % c ) (a,c)\rightarrow(a\%c,c)\rightarrow(c,a\%c) (a,c)→(a%c,c)→(c,a%c) ，因此递归层数为O ( L o g V ) O(LogV) O(LogV) 。
• 时间复杂度O ( T K 4 L o g V ) O(TK^4LogV) O(TK4LogV) 。

【【类型】做题记录|【LOJ138】类欧几里得算法】【代码】

#include using namespace std; const int MAXN = 15; const int P = 1e9 + 7; typedef long long ll; typedef long double ld; typedef unsigned long long ull; template void chkmax(T &x, T y) {x = max(x, y); } template void chkmin(T &x, T y) {x = min(x, y); } template void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template void writeln(T x) { write(x); puts(""); } struct info { int a[MAXN][MAXN]; }; int sum[MAXN][MAXN]; int binom[MAXN][MAXN]; int power(int x, int y) { if (y == 0) return 1; int tmp = power(x, y / 2); if (y % 2 == 0) return 1ll * tmp * tmp % P; else return 1ll * tmp * tmp % P * x % P; } void update(int &x, int y) { x += y; if (x >= P) x -= P; } info func(int n, int a, int b, int c) { assert(n >= 0 && a >= 0 && b >= 0 && c >= 0); info ans; memset(ans.a, 0, sizeof(ans.a)); if (a == 0 || (1ll * a * n + b) / c == 0) { for (int k1 = 0; k1 <= 10; k1++) { int mul = 0, now = 1; for (int i = 0; i <= k1 + 1; i++) { update(mul, 1ll * now * sum[k1][i] % P); now = 1ll * now * n % P; } int base = (1ll * a * n + b) / c % P; now = 1; for (int k2 = 0; k1 + k2 <= 10; k2++) { ans.a[k1][k2] = 1ll * now * mul % P; now = 1ll * now * base % P; } } return ans; } if (a >= c) { info tmp = func(n, a % c, b, c); for (int k1 = 0; k1 <= 10; k1++) for (int k2 = 0; k1 + k2 <= 10; k2++) { int now = 1, base = a / c; for (int i = 0; i <= k2; i++) { update(ans.a[k1][k2], 1ll * binom[k2][i] * now % P * tmp.a[k1 + i][k2 - i] % P); now = 1ll * now * base % P; } } return ans; } if (b >= c) { info tmp = func(n, a, b % c, c); for (int k1 = 0; k1 <= 10; k1++) for (int k2 = 0; k1 + k2 <= 10; k2++) { int now = 1, base = b / c; for (int i = 0; i <= k2; i++) { update(ans.a[k1][k2], 1ll * binom[k2][i] * now % P * tmp.a[k1][k2 - i] % P); now = 1ll * now * base % P; } } return ans; } int m = (1ll * a * n + b) / c; info tmp = func(m - 1, c, c - b - 1, a); for (int k1 = 0; k1 <= 10; k1++) { int all = 0, now = 1; for (int i = 0; i <= k1 + 1; i++) { update(all, 1ll * now * sum[k1][i] % P); now = 1ll * now * n % P; } for (int k2 = 0; k1 + k2 <= 10; k2++) { ans.a[k1][k2] = 1ll * power(m, k2) * all % P; for (int i = 0; i <= k2 - 1; i++) for (int j = 0; j <= k1 + 1; j++) { int coef = 1ll * binom[k2][i] * sum[k1][j] % P; update(ans.a[k1][k2], P - 1ll * coef * tmp.a[i][j] % P); } } } return ans; } void Lagrange(int n, int *x, int *y, int *a) { static int p[MAXN], q[MAXN]; memset(p, 0, sizeof(p)); p[0] = 1; for (int i = 1; i <= n; i++) { for (int j = i - 1; j >= 0; j--) { p[j + 1] = (p[j + 1] + p[j]) % P; p[j] = (P - 1ll * p[j] * x[i] % P) % P; } } for (int i = 1; i <= n; i++) { memset(q, 0, sizeof(q)); for (int j = n - 1; j >= 0; j--) q[j] = (p[j + 1] + 1ll * q[j + 1] * x[i]) % P; int now = 1; for (int j = 1; j <= n; j++) if (j != i) now = 1ll * now * (x[i] - x[j]) % P; now = power((P + now) % P, P - 2); for (int j = 0; j <= n; j++) q[j] = 1ll * q[j] * now % P; for (int j = 0; j <= n; j++) a[j] = (a[j] + 1ll * q[j] * y[i]) % P; } } int main() { for (int i = 0; i <= 10; i++) { static int pos[MAXN], now[MAXN]; now[0] = power(0, i); for (int j = 1; j <= i + 2; j++) { now[j] = (now[j - 1] + power(j, i)) % P; pos[j] = j; } Lagrange(i + 2, pos, now, sum[i]); } for (int i = 0; i <= 10; i++) { binom[i][0] = 1; for (int j = 1; j <= i; j++) binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j]; } int T; read(T); while (T--) { int n, a, b, c, k1, k2; read(n), read(a), read(b), read(c), read(k1), read(k2); writeln(func(n, a, b, c).a[k1][k2]); } return 0; }

推荐阅读

• 

  顺丰速递单号查询 查快递信息官网 顺丰速递单号查询 查快递信息
• 

  不急不躁就是最好的状态
• 

  小朋友过生日送什么礼物好
• 

  诗姐诗妹接龙
• 

  投稿|淘系女装脱去“黄金甲”
• 

  广仁医院是不是私立医院 杭州广仁医院怎么样
• 

  新手如何开自动挡汽车呢图片 新手如何开自动挡汽车呢
• 

  可以带上飞机的行李箱尺寸图片 可以带上飞机的行李箱尺寸
• 

  如何正确晒太阳补钙
• 

  subverse阿根廷怎么买 subverse阿根廷区买法一览
• 

  三菱电机空调显示UL处理方法,是因为这些原因
• 

  捷达vs5的发动机和大众哪款一样 捷达vs5发动机和大众哪个一样
• 

  苦瓜怎么做不苦 苦瓜怎么吃不苦
• 

  专家教你节后怎样清理肠胃
• 

  火车的英语怎么写 火车翻译成英文
• 

  go语言与java Go语言与环境
• 

  柞树叶
• 

  华为mate40价格多少？华为mate40pro内屏坏了多少钱
• 

  尼康fm2镜头怎么装 尼康fm2相机修理
• 

  iphone12|华为手机销量跌42%，苹果暴涨22%，中国市场不喜欢华为了？