自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:19:10，当前版本为作者最后更新于2020-08-09 15:45:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一道经典的莫比乌斯反演练习题。

---

这里规定一下变量名：

题目中的 $d \rightarrow k$。

题目中的 $w \rightarrow n$。

题目中的 $n \rightarrow N$。

---

考虑构造：

$$F(n)=\sum_{i=1}^{n} i^k$$ $$G(n)=\sum_{i=1}^{n} i^k[\gcd(i, n)=1]$$

则我们最后想要的答案为 $G(N)$。

不难发现有：

$$F(n)=\sum_{d|n} d^k G\left(\frac{n}{d}\right)$$

那么我们考虑对其做莫比乌斯反演，则有：

$$G(n)=\sum_{d|n} \mu(d)d^k F\left(\frac{n}{d}\right) $$

注意到 $F(n)$ 事实上是关于 $n$ 的 $k+1$ 次多项式，所以可以将其表示为 $F(n)=\sum_{i=0}^{k+1}f_i n^i$ 的形式。

那么对上面的式子展开即得：

$$G(n)=\sum_{d|n} \mu(d)d^k \sum_{i=0}^{k+1} f_i\left(\frac{n}{d}\right)^i $$$$G(n)= \sum_{i=0}^{k+1} f_i n^i \sum_{d|n} \mu(d)d^{k-i} $$

若 $n$ 能够分解为 $\prod p_i^{a_i}$ 的形式，由于 $\mu(d)d^{k-i}$ 必然是一个积性函数，所以后面的一个 $\sum$ 可以写成：

$$G(n)= \sum_{i=0}^{k+1} f_i n^i \prod_{p_j|n} \sum_{t=0}^{a_j}\mu(p_j^t)p_j^{t(k-i)} $$

注意到 $\mu$ 在质数幂次上次取值有：

$$\mu(p^k)= \begin{cases} 1 \qquad & k=0\\ -1 \qquad & k=1\\ 0 \qquad & k>1 \end{cases} $$

所以最后一个 $\sum$ 中的 $t$ 至多枚举到 $1$。即原式可化为：

$$G(n)= \sum_{i=0}^{k+1} f_i n^i \prod_{p_j|n} \left(1-p_j^{k-i}\right) $$

而我们想要的就是 $G(N)$，而 $N$ 也是以其质因数分解的形式给出，则剩下的问题是插值出我们要的自然数幂和的多项式。

这个东西的一般暴力方法可以用拉格朗日插值做到 $O(n^3)$ 或者 $O(n^2)$。主要原理就是这个式子：

对于一个 $k$ 次多项式，在给定其 $k+1$ 个点值 $(x_i,y_i=F(x_i))$ 的情况下，我们可以插出其多项式为：

$$F(x)=\sum_{i=1}^{k+1} y_i \prod_{j \ne i} \frac{x-x_j}{x_i-x_j} $$

然后纯粹模拟多项式乘法和多项式加法，就可以做到 $O(k^3)$。但是如果我们预处理出 $\prod_{i=1}^{k+1}(x-x_j)$ 这个多项式，每次加的时候先除掉一个单项式再乘常数，最后做加法，这样就可以做到 $O(k^2)$ 插出这个多项式。由于此题中 $k \leq 100$，所以使用最暴力朴素的算法即可。

至此，整个问题就可以在 $O(k^3+kn)$ 或者 $O(k^2+kn)$ 的时间复杂度内解决。

部分代码如下：

const int mod = 1e9 + 7;

inline int Mod(int x) { return x >= mod ? x - mod : x; }
inline void Add(int &x, int y) { x += y, x -= x >= mod ? mod : 0; }
inline int fsp(int x, int k = mod - 2) {
	int s = 1;
	while(k) {
		if(k & 1) s = 1LL * s * x % mod;
		x = 1LL * x * x % mod, k >>= 1;
	} return s;
}

int f[110];
int p[1010];

// {{{ Lagrange
int A[110];
int len;

inline void Poly_Mul(int a, int b) {
	++len;
	for(int i = len; i >= 1; i--)
		A[i] = (1LL * A[i] * b + 1LL * A[i - 1] * a) % mod;
	A[0] = 1LL * A[0] * b % mod;
}

inline void Num_Mul(int v) {
	for(int i = 0; i <= len; i++)
		A[i] = 1LL * A[i] * v % mod;
}

inline void Poly_Add() {
	for(int i = 0; i <= len; i++)
		Add(f[i], A[i]), A[i] = 0;
	len = 0, A[0] = 1;
}

inline void init(int k) {
	A[0] = 1, len = 0;
	int S = 0;
	for(int i = 1; i <= k + 3; i++) {
		Add(S, fsp(i, k));
		int mul = fsp(S);
		for(int j = 1; j <= k + 3; j++) {
			if(i == j) continue;
			Poly_Mul(1, mod - j);
			mul = 1LL * mul * (i + mod - j) % mod;
		} Num_Mul(fsp(mul)), Poly_Add();
	}
}
// }}}

int main() {
	int k = ri, n = ri, N = 1;
	for(int i = 1; i <= n; i++) p[i] = ri, N = 1LL * N * fsp(p[i], ri) % mod;

	init(k);

	int res = 0, pw = N;
	for(int i = 1; i <= k + 3; i++) {
		int ans = 1LL * pw * f[i] % mod;
		pw = 1LL * pw * N % mod;
		for(int j = 1; j <= n; j++)
			ans = 1LL * ans * (1 + mod - fsp(p[j], k - i + mod - 1)) % mod;
		Add(res, ans);
	} cout << res << endl;
	return 0;
}