题解 P6271 【[湖北省队互测2014]一个人的数论】
CYJian
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)$ 的时间复杂度内解决。
部分代码如下:
```cpp
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;
}
```