P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题

P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题

记 $s_n=\sum _{i=1}^{n}i$ 。

Type 0

$\mathrm{lcm}(i,j)=\frac{ij}{gcd(i,j)}$ 。将分子分母每个部分分开计算，$X(A,B,C)=\prod _{i=1}^A\prod _{j=1}^B\prod _{k=1}^{C}i$ ，$Y(A,B,C)=\prod _{i=1}^A\prod _{j=1}^B\prod _{k=1}^C(i,j)$ 。那么答案为 $\frac{X(A,B,C)X(B,A,C)}{Y(A,B,C)Y(A,C,B)}$ 。

$$X(A,B,C)=(A!{)}^{BC}$$

$$\begin{array}{rl}Y(A,B,C)& =\prod _{i=1}^A\prod _{j=1}^B\prod _{k=1}^C(i,j)\\ & =(\prod _{i=1}^A\prod _{j=1}^B(i,j){)}^C\\ & =(\prod _{d=1}^n\prod _{i=1}^A\prod _{j=1}^B{d}^{[(i,j)=d]}{)}^C\\ & =(\prod _{d=1}^n{d}^{\sum _{i=1}^A\sum _{j=1}^B[(i,j)=d]}{)}^C\\ & =(\prod _{d=1}^n{d}^{\sum _{k=1}^{\lfloor \frac{n}{d}\rfloor }\mu (k)\lfloor \frac{A}{kd}\rfloor \lfloor \frac{B}{kd}\rfloor }{)}^C\\ & =(\prod _{T=1}^n(\prod _{d|T}{d}^{\mu (\frac{T}{d})}{)}^{\lfloor \frac{A}{T}\rfloor \lfloor \frac{B}{T}\rfloor }{)}^C\end{array}$$

其中 $\prod _{d|T}{d}^{\mu (\frac{T}{d})}$ 可以用 $n\ln n$ 时间预处理，做前缀积，可以数论分块。

Type 1

$$X(A,B,C)=\prod _{i=1}^A\prod _{j=1}^B\prod _{k=1}^C{i}^{ijk}=(\prod _{i=1}^A{i}^i{)}^{s_B{s}_C}$$

$$\begin{array}{rl}Y(A,B,C)& =\prod _{i=1}^A\prod _{j=1}^B\prod _{k=1}^C(i,j{)}^{ijk}\\ & =(\prod _{i=1}^A\prod _{j=1}^B(i,j{)}^{ij}{)}^{s_C}\\ & =(\prod _{d=1}^n\prod _{i=1}^A\prod _{j=1}^B{d}^{ij[(i,j)=d]}{)}^{s_C}\\ & =(\prod _{d=1}^n{d}^{\sum _{i=1}^A\sum _{j=1}^{B}ij[(i,j)=d]}{)}^{s_C}\\ & =(\prod _{d=1}^n{d}^{\sum _{k=1}^{\lfloor \frac{n}{d}\rfloor }\mu (k)d^2{k}^2{s}_{\lfloor \frac{A}{kd}\rfloor }{s}_{\lfloor \frac{B}{kd}\rfloor }}{)}^{s_C}\\ & =(\prod _{T=1}^n(\prod _{d|T}{d}^{\mu (\frac{T}{d})T^2}{)}^{s_{\lfloor \frac{A}{kd}\rfloor }{s}_{\lfloor \frac{B}{kd}\rfloor }}{)}^{s_C}\end{array}$$

其中 $\prod _{d|T}{d}^{\mu (\frac{T}{d})T^2}$ 可以用 $n\ln n$ 时间预处理，做前缀积，可以数论分块。

Type 2

$$\begin{array}{r}\prod _{i=1}^A\prod _{j=1}^B\prod _{k=1}^C(\frac{\mathrm{lcm}(i,j)}{(i,k)}{)}^{(i,j,k)}=\prod _{d=1}^n(\prod _{i=1}^{\lfloor \frac{A}{d}\rfloor }\prod _{i=1}^{\lfloor \frac{B}{d}\rfloor }\prod _{k=1}^{\lfloor \frac{C}{d}\rfloor }\frac{\mathrm{lcm}(i,j)}{(i,k)}{)}^{\phi (d)}\end{array}$$

中间部分为 Type 0 答案，数论分块套数论分块，复杂度 $O(n^{\frac{3}{4}}{\log }^{2}p)$ 。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
typedef long long LL;
const int N = 1e5 + 10;
bool vis[N];
struct FastMod
{
    typedef unsigned long long ULL;
    typedef unsigned __int128 UL;
    bool flag;
    int d, l; ULL m;
    FastMod () {}
    FastMod (int _d) : d(_d)
    {
        l = 64 - __builtin_clzll(d - 1);
        const UL i = 1;
        UL M = ((i << (64 + l)) + (i << l)) / d;
        if (M < (i << 64)) flag = 1, m = M;
        else flag = 0, m = M - (i << 64);
    }
    friend ULL operator/(ULL n, const FastMod &m)
    {
        if (m.flag) return (UL)n * m.m >> 64 >> m.l;
        ULL t = (UL)n * m.m >> 64;
        return (((n - t) >> 1) + t) >> (m.l - 1);
    }
    template <class Type>
    friend Type operator % (Type n, const FastMod &m)
    {
        bool flag = false;
        if (n < 0) flag = true, n = ~n + 1;
        n -= n / m * m.d;
        if (flag) n = ~n + 1;
        return n;
    }
} mod, _mod;
int Mod;
int cnt, p[N], mu[N], phi[N], s[N];
int binpow (int b, int k = Mod - 2)
{
    if (k < 0) k += Mod - 1;
    int res = 1;
    for (; k; k >>= 1, b = (LL)b * b % mod)
        if (k & 1) res = (LL)res * b % mod;
    return res;
}
void init ()
{
    vis[1] = true;
    mu[1] = 1, phi[1] = 1;
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i])
        {
            p[++cnt] = i;
            mu[i] = -1, phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * p[j] < N; ++j)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0)
                { phi[i * p[j]] = phi[i] * p[j]; break; }
            mu[i * p[j]] = -mu[i], phi[i * p[j]] = phi[i] * phi[p[j]];
        }
    }
    for (int i = 1; i < N; ++i)
        s[i] = (s[i - 1] + i) % _mod;
    for (int i = 2; i < N; ++i)
        phi[i] = (phi[i - 1] + phi[i]) % _mod;
}
namespace Type0
{
    int f[N], g[N];
    void init ()
    {
        f[0] = 1;
        for (int i = 1; i < N; ++i)
            f[i] = (LL)f[i - 1] * i % mod;
        for (int i = 0; i < N; ++i) g[i] = 1;
        for (int i = 1; i < N; ++i) if (mu[i])
            for (int j = 1; i * j < N; ++j)
                g[i * j] = (LL)g[i * j] * binpow(j, mu[i]) % mod;
        for (int i = 1; i < N; ++i)
            g[i] = (LL)g[i] * g[i - 1] % mod;
    }
    int X (int n, int a, int b) { return binpow(f[n], (LL)a * b % _mod); }
    int Y (int n, int m, int k)
    {
        int res = 1;
        if (n > m) swap(n, m);
        for (int l = 1, r; l <= n; l = r + 1)
        {
            int a = n / l, b = m / l;
            r = min(n / a, m / b);
            res = (LL)res * binpow((LL)g[r] * binpow(g[l - 1]) % mod, (LL)a * b % _mod) % mod;
        }
        return binpow(res, k);
    }
    int ans(int A, int B, int C)
        { return (LL)X(A, B, C) * X(B, A, C) % mod * binpow((LL)Y(A, B, C) * Y(A, C, B) % mod) % mod; }
}
namespace Type1
{
    int f[N], g[N];
    void init ()
    {
        f[0] = 1;
        for (int i = 1; i < N; ++i)
            f[i] = (LL)f[i - 1] * binpow(i, i) % mod;
        for (int i = 0; i < N; ++i) g[i] = 1;
        for (int i = 1; i < N; ++i) if (mu[i])
            for (int j = 1; i * j < N; ++j)
                g[i * j] = (LL)g[i * j] * binpow(j, (LL)(i * j) * (i * j) * mu[i] % _mod) % mod;
        for (int i = 1; i < N; ++i)
            g[i] = (LL)g[i] * g[i - 1] % mod;
    }
    int X (int n, int a, int b) { return binpow(f[n], (LL)s[a] * s[b] % _mod); }
    int Y (int n, int m, int k)
    {
        int res = 1;
        if (n > m) swap(n, m);
        for (int l = 1, r; l <= n; l = r + 1)
        {
            int a = n / l, b = m / l;
            r = min(n / a, m / b);
            res = (LL)res * binpow((LL)g[r] * binpow(g[l - 1]) % mod, (LL)s[a] * s[b] % _mod) % mod;
        }
        return binpow(res, s[k]);
    }
    int ans(int A, int B, int C)
        { return (LL)X(A, B, C) * X(B, A, C) % mod * binpow((LL)Y(A, B, C) * Y(A, C, B) % mod) % mod; }
}
namespace Type2
{
    int ans (int A, int B, int C)
    {
        int n = min({A, B, C});
        int res = 1;
        for (int l = 1, r; l <= n; l = r + 1)
        {
            int a = A / l, b = B / l, c = C / l;
            r = min({A / a, B / b, C / c});
            res = (LL)res * binpow(Type0::ans(a, b, c), phi[r] - phi[l - 1]) % mod;
        }
        return res;
    }
}
int main ()
{
    int T; read(T, Mod);
    mod = FastMod(Mod), _mod = FastMod(Mod - 1);
    init();
    Type0::init(), Type1::init();
    for (int A, B, C; T; --T)
    {
        read(A, B, C);
        write((Type0::ans(A, B, C) + Mod) % Mod), putchar(' ');
        write((Type1::ans(A, B, C) + Mod) % Mod), putchar(' ');
        write((Type2::ans(A, B, C) + Mod) % Mod), puts("");
    }
    return 0;
}