题解 P6271 【[湖北省队互测2014]一个人的数论】

CYJian

2020-08-09 15:45:01

Solution

一道经典的莫比乌斯反演练习题。 --- 这里规定一下变量名: 题目中的 $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; } ```