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

· · 题解

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

这里规定一下变量名：

题目中的 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;
}