题目链接
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}\) 相减，得到： $$\begin{aligned}(n + 1)^{k + 1}-n^{k + 1} &= \left(\sum_{i = 0}^{k + 1}{\binom{k + 1}{i}}n^i\right) - n^{k + 1} \ &= \sum_{i = 0}^k\binom{k + 1}{i}n^i \end{aligned}$$ 其中，\((n + 1)^{k + 1} = \sum_\limits{i = 0}^{k + 1}\binom{k + 1}{i}n^i\) 用到了二项式定理。
- 多项式 \(n^{k + 1}\)与 \((n - 1)^{k + 1}\) 相减，得到： $$n^{k + 1} - (n - 1)^{k + 1} = \sum_{i = 0}^k \binom{k + 1}{i}(n - 1)^i$$
- \(\cdots\)
- 多项式 \(1^{k + 1}\) 与 \(0^{k + 1}\) 相减，得到 $$1^{k + 1} - 0^{k + 1} = \sum_{i = 0}^k\binom{k + 1}{i}0^i$$
- 将上面所有式子相加，得到 $$(n + 1)^{k + 1} = \sum_{i = 0}^{k}\binom{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}\right)^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\n", answer);
return 0;
}