题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=3601
题解
首先还是基本的推式子：
令 (g(x) = sum_limits{i = 1}^x i^d)，那么原式即为 $ sum_limits{k |n} mu(k)k^d g(frac{n}{k})$。
关于函数 (g(x))，这其实是一个关于 (x) 的 (d + 1) 次多项式。在这里我们作简要证明。也就是我们要证明「前 (n) 个正整数的 (k) 次幂之和是关于 (n) 的 (k+1) 次多项式」。这里把我之前的一篇博客中的内容放出来。证明如下：
令 (S(n, k) = sum_limits{i = 1}^{n} i^k)，那么我们的目的无非是要证明 (S(n, k)) 与一个关于 (n) 的 (k + 1) 次多项式存在某种等式关系。我们作如下考虑：
- 我们将两个关于 (n) 的 (k + 1) 次多项式 ((n + 1)^{k + 1}) 与 (n^{k + 1}) 相减，得到： $$egin{aligned}(n + 1)^{k + 1}-n^{k + 1} &= left(sum_{i = 0}^{k + 1}{inom{k + 1}{i}}n^i ight) - n^{k + 1} &= sum_{i = 0}^kinom{k + 1}{i}n^i end{aligned}$$ 其中，((n + 1)^{k + 1} = sum_limits{i = 0}^{k + 1}inom{k + 1}{i}n^i) 用到了二项式定理。
- 多项式 (n^{k + 1})与 ((n - 1)^{k + 1}) 相减，得到： $$n^{k + 1} - (n - 1)^{k + 1} = sum_{i = 0}^k inom{k + 1}{i}(n - 1)^i$$
- (cdots)
- 多项式 (1^{k + 1}) 与 (0^{k + 1}) 相减，得到 $$1^{k + 1} - 0^{k + 1} = sum_{i = 0}^kinom{k + 1}{i}0^i$$
- 将上面所有式子相加，得到 $$(n + 1)^{k + 1} = sum_{i = 0}^{k}inom{k + 1}{i}S(n, i)$$
当 (k = 0) 时，(S(n, 0)) 显然是一个关于 (n) 的 (1) 次多项式。通过移项，即可得到：对于任意的 (k(k > 0))，均满足 (S(n, k)) 是一个关于 (n) 的 (k + 1) 次多项式。
同时，我们还能推广该结论得到：若 (f(x)) 是一个关于 (x) 的任意 (k) 次多项式，(g(x)) 满足 (g(x) = sum_limits{i = 1}^{x} f(i))，那么 (g(x)) 也是一个关于 (x) 的 (k + 1) 次多项式。
其证明显然，我们只需要将 (f(i)) 的各次项拆开统计到 (g(x)) 中，那么 (g(x)) 就是 (k + 1) 个形如 (a sum_limits{i = 1}^{x}i^b (0 leq b leq k)) 的关于 (x) 的 (b + 1) 次多项式的和，即关于 (x) 的 (k + 1) 次多项式。
既然 (g(x)) 已经是一个关于 (x) 的 (d + 1) 次多项式，那么我们就可以将 (g(x)) 写成多项式的一般形式，即：(g(x) = sum_limits{i = 0}^{d + 1}a_{i}x^i)。由于 (d leq 100)，因此每一项的系数 (a_i) 可以通过高斯消元求得，复杂度是可接受的。我们将 (g(x)) 代入原答案式，得到：
令 (h_i(x) = sum_limits{k | x} mu(k) k^d left(frac{x}{k} ight)^i)，显然，(h_i) 是两个积性函数的狄利克雷卷积。因此 (h_i) 本身也是一个积性函数，由于 (n) 的唯一分解式为 (n = prod_limits{k = 1}^{w} p_k ^{alpha_k})，故有 (h_i(n) = prod_limits{k = 1}^w h_i(p_k^{alpha_k}))。
考虑如何求单个 (h_i(p ^{alpha}))：
由于当 (j = 0) 时，(mu(p^j) = 1)；当 (j = 1) 时，(mu(p^j) = -1)；当 (j > 1) 时，(mu(p^j) = 0)。故有：
这样，单个 (h_i(p ^ {alpha})) 就能用快速幂在 (O(log alpha)) 的时间内求出。因此，解决整个问题的时间复杂度为 (O(d^3 + dw log alpha))。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, mod = 1e9 + 7;
void add(int& x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
void sub(int& x, int y) {
x -= y;
if (x < 0) {
x += mod;
}
}
int mul(int x, int y) {
return (long long) x * y % mod;
}
int qpow(int v, int p) {
int result = 1;
for (; p; p >>= 1, v = mul(v, v)) {
if (p & 1) {
result = mul(result, v);
}
}
return result;
}
int d, w, p[N], alpha[N], a[N][N];
void get_coefficient() {
int sum = 0;
for (int i = 0; i <= d + 1; ++i) {
add(sum, qpow(i, d));
a[i][d + 2] = sum;
int pow_value = 1;
for (int j = 0; j <= d + 1; ++j) {
a[i][j] = pow_value;
pow_value = mul(pow_value, i);
}
}
for (int i = 0; i <= d + 1; ++i) {
int rev = i;
for (int j = i + 1; j <= d + 1; ++j) {
if (a[j][i]) {
rev = j;
break;
}
}
if (rev != i) {
for (int j = i; j <= d + 2; ++j) {
swap(a[rev][j], a[i][j]);
}
}
for (int j = i + 1; j <= d + 1; ++j) {
int p = mul(a[j][i], qpow(a[i][i], mod - 2));
for (int k = i; k <= d + 2; ++k) {
sub(a[j][k], mul(a[i][k], p));
}
}
}
for (int i = d + 1; ~i; --i) {
for (int j = i + 1; j <= d + 1; ++j) {
sub(a[i][d + 2], mul(a[i][j], a[j][d + 2]));
}
a[i][d + 2] = mul(a[i][d + 2], qpow(a[i][i], mod - 2));
}
}
int g(int i, int j) {
int p_i = p[j], alpha_i = alpha[j];
int c1 = (long long) alpha_i * i % (mod - 1);
int c2 = (c1 + d - i + mod - 1) % (mod - 1);
return (qpow(p_i, c1) - qpow(p_i, c2) + mod) % mod;
}
int main() {
scanf("%d%d", &d, &w);
get_coefficient();
for (int i = 1; i <= w; ++i) {
scanf("%d%d", &p[i], &alpha[i]);
}
int answer = 0;
for (int i = 0; i <= d + 1; ++i) {
int result = a[i][d + 2];
for (int j = 1; j <= w; ++j) {
result = mul(result, g(i, j));
}
add(answer, result);
}
printf("%d
", answer);
return 0;
}