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

Mobius127 · 2021-05-26 13:05:33 · 题解

5 月开的，现在写完。。。~~足以显示我有多咕~~

题目传送门

提前开坑？

约定:

如无特殊说明，本文的 n 为 ABC 的值域范围。
假定 sum(x)=\sum_{y=1}^{x} y 。
由于不想炸掉 \LaTeX ，把一部分整除的直接写成了除法。
函数 \varepsilon(x)=[x=1] 直接简写成 [x] 。

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} (\frac{i \times j}{\gcd(i, j) \times \gcd(i, k)})^{f(type)}$$ 再把幂给套开。 $$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} \frac{(i \times j)^{f(type)}}{[\gcd(i, j) \times \gcd(i, k)]^{f(type)}} $$ 再把连乘积放进分数里面（连乘积有个好处就是分子分母可以拆开来计算贡献）。 $$\frac{\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}(i \times j)^{f(type)}}{\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}[\gcd(i, j) \times \gcd(i, k)]^{f(type)}}$$ 显然可以把分母看成两个类似于这样的东西相乘： $$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} \gcd(i, j)^{f(type)}$$ 同时，分子也可以类似同化： $$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} i ^{f(type)}$$ 那么，我们只要计算出分子和分母的值，再用分子乘上分母的逆元即可。 ~~但是并没有到很重要的环节~~ 直接分 $type$ 去推柿子！！1 ### Segment 1: $type=0

考虑分子：

\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} i^{1}

显然每个 i 都被乘了 B \times C 次。

那么就是 \prod_{i=1}^{A} i^{B \times C} = (A!)^{B \times C} 。

预处理阶乘后快速幂可做到 \log n 。

再看分母：

\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} \gcd(i, j)^{1}=\prod_{i=1}^{A}\prod_{j=1}^{B} \gcd(i, j)^{C}

带着幂并不好推，把 C 提出。

(\prod_{i=1}^{A}\prod_{j=1}^{B} \gcd(i, j))^{C}

然后就变成了莫反基本套路。

\Large \left ({\normalsize \prod_{d=1} d }^{\sum_{d'=1} \mu(d') \left \lfloor \frac{A}{dd'} \right \rfloor \left \lfloor \frac{B}{dd'} \right \rfloor } \right ) ^{C}

来一发 T=dd' 。

{\Large \left ( \prod_{T=1}{\large \left ( {\normalsize \prod_{d|T} d^{\mu(T/d)}} \right ) }^{\left \lfloor \frac{A}{T} \right \rfloor \left \lfloor \frac{B}{T} \right \rfloor } \right ) }^C

注意到第二对括号里的东西对于每一个 T 是一定的，可以 O(n \ln n) 筛出来。

即令 f(T)=\prod_{d|T} d^{\mu(T/d)}

预处理完后就可以愉快地跑整除分块O(\sqrt{n} \log n)啦~

Segment 2: type=1

考虑分子：

\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} i^{i \times j \times k}

显然这个 j,k 可以提出。

\prod_{i=1}^{A} i^{i \times sum(B) \times sum(C) }=(\prod_{i=1}^{A} i^{i})^{sum(B) \times sum(C)}

预处理出括号内的东西后套个快速幂，时间复杂度 O(\log n)。

再看分母：

\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} \gcd(i, j)^{i \times j \times k}={\Large \left ({\normalsize \prod_{i=1}^{A}\prod_{j=1}^{B} \gcd(i, j)^{i \times j}} \right ) } ^{sum(C)}

扔掉外面的幂，继续推里面的，都是莫反的基本套路了。

\prod_{d=1}^{A}\prod_{i=1}^{A/d}\prod_{j=1}^{B/d} d^{ij \times d^2 [gcd(i,j)]}

第三个 \prod 可以拆掉。

\prod_{d=1}^{A}\prod_{i=1}^{A/d}d^{\mu(i) \times d^2 \times i^2 \times sum(A/di) \times sum(B/di)}

熟悉的连乘项 T=di 。

\prod_{T=1}^{A} {\Large \left ({\large \left ({\normalsize \prod_{d|T} d^{\mu(T/d)}} \right )^{T^2} } \right ) ^{sum(A/T) \times sum(B/T)}}

看到了吗！我们之前出的 f(T) 出现了！！1

\prod_{T=1}^{A} { \left (f(T)^{T^2} \right ) ^{sum(A/T) \times sum(B/T)}}

同样多预处理一个平方就可以做到单次 O(\sqrt{n} \log n) 了。

不要忘记我们之前丢掉的幂！！1

Segment 3: type=2

提前 FBI WARNING。

考虑分子：

\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} i^{\gcd(i,j,k)}

\prod_{i=1}^{A}i^{\sum_{j=1}^{B}\sum_{k=1}^{C}\gcd(i,j,k)}

滚过去看指数。

\sum_{i=1}^{B}\sum_{j=1}^{C}\gcd(n,i,j)

大力枚举 \gcd(i, j, n)

\sum_{d=1}d\sum_{i=1}^{B/d}\sum_{j=1}^{C/d}[\gcd(i, j, n/d][d|n]

$$\sum_{d|n}d\sum_{i=1}^{B/d}\sum_{j=1}^{C/d}[\gcd(i, j, n/d)]=\sum_{d|n}d\sum_{dd'|n}^{B} \mu(d') \left \lfloor \frac{B}{dd'} \right \rfloor \left \lfloor \frac{C}{dd'} \right \rfloor $$ 梅开 n 度 ... $$\sum_{T|n}\left \lfloor \frac{B}{T} \right \rfloor \left \lfloor \frac{C}{T} \right \rfloor \sum_{d|T} \mu(d) (T/d)$$ 第二个 $\sum$ 其实就是欧拉反演 $\varphi = \mu * id$ 。 $$\sum_{T|n}\left \lfloor \frac{B}{T} \right \rfloor \left \lfloor \frac{C}{T} \right \rfloor \varphi(T)$$ 把这东西代回去。 $$\prod_{i=1}^{A}i^{\sum_{T|i}\left \lfloor \frac{B}{T} \right \rfloor \left \lfloor \frac{C}{T} \right \rfloor \varphi(T)}$$ 把 $\sum$ 放下来变成 $\prod$ 。 $$\prod_{i=1}^{A}\prod_{T|i}i^{\left \lfloor \frac{B}{T} \right \rfloor \left \lfloor \frac{C}{T} \right \rfloor \varphi(T)}$$ $T$ 在里面计算很难，不妨改变枚举顺序，枚举 $T$ 后枚举其倍数： $$\prod_{T=1}^{A}(T^{\left \lfloor \frac{A}{T} \right \rfloor } \times \prod_{i=1}^{\left \lfloor \frac{A}{T} \right \rfloor } i) ^{\left \lfloor \frac{B}{T} \right \rfloor \left \lfloor \frac{C}{T} \right \rfloor \varphi(T)}$$ 里面的 $\prod$ 可以化为阶乘。 $$\prod_{T=1}^{A}(T^{\varphi(T)} ) ^{\left \lfloor \frac{A}{T} \right \rfloor \left \lfloor \frac{B}{T} \right \rfloor \left \lfloor \frac{C}{T} \right \rfloor }\times (\left \lfloor \frac{A}{T} \right \rfloor !)^{\left \lfloor \frac{B}{T} \right \rfloor \left \lfloor \frac{C}{T} \right \rfloor \varphi(T)}$$ 预处理一波 $\varphi$ 的前缀和以及 $\varphi$ 的指数幂即可 $O(\sqrt{n}\log n)$ 啦。接下来是最恐怖的柿子。。。 $$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} \gcd(i, j)^{\gcd(i,j,k)}$$ 考虑枚举 $\gcd(i,j,k)$ 。由于 $\gcd(i, j, k)=\gcd(\gcd(i, j), k)$，所以我们枚举 $\gcd(i, j)$。 $$=\prod_{d=1}^{A} d^{\sum_{i=1}^{A} \sum_{j=1}^{B}[\gcd(i, j)=d]\times (\sum_{k=1}^{C}\gcd(d, k))}$$ 显然幂的指数珂以分开计，套路变换不多说。。。 $$=\prod_{d=1}^{A} d^{(\sum_{i=1}^{A/d} \sum_{j=1}^{B/d}[\gcd(i, j)]) \times (\sum_{k=1}^{C}\gcd(d, k))}$$ $$=\prod_{d=1}^{A} d^{(\sum_{d'|\min(A/d, B/d)} \mu(d') \left \lfloor \frac{A}{dd'} \right \rfloor \left \lfloor \frac{B}{dd'} \right \rfloor ) \times (\sum_{k=1}^{C}\gcd(d, k))}$$ 这里有个很妙的一个点：将 $\sum$ 下放，仍然是 $T=dd'$。 $$=\prod_{T=1}^{A} (\prod_{d|T} d^{\mu(T/d) \times \sum_{k=1}^{C}\gcd(d, k)})^{\left \lfloor \frac{A}{T} \right \rfloor \left \lfloor \frac{B}{T} \right \rfloor }$$ 对于右上角的 $\sum_{k=1}^{C}\gcd(d, k)$，右转去 [这里](https://www.luogu.com.cn/problem/P2303) $=\sum_{d'|d} \left \lfloor \frac{C}{d'} \right \rfloor \varphi(d')$，套回去并同样将 $\sum$ 下放。 $$=\prod_{T=1}^{A} (\prod_{d|T} \prod_{d'|d}d^{\mu(T/d) \times \left \lfloor \frac{C}{d'} \right \rfloor \varphi(d')})^{\left \lfloor \frac{A}{T} \right \rfloor \left \lfloor \frac{B}{T} \right \rfloor }$$ 这里有个阴间的做法：把 $d$ 变成 $d' \times \frac{d}{d'}$。对于 $d'$： $$\prod_{T=1}^{A} (\prod_{d|T} \prod_{d'|d} d'^{\mu(T/d) \times \left \lfloor \frac{C}{d'} \right \rfloor \varphi(d')})^{\left \lfloor \frac{A}{T} \right \rfloor \left \lfloor \frac{B}{T} \right \rfloor }$$ 枚举 $T=d'

=\prod_{T=1}^{A} T^{\varphi(T)\left \lfloor \frac{C}{T} \right \rfloor\sum_{d=1}^{A/T} \left \lfloor \frac{A}{Td} \right \rfloor \left \lfloor \frac{B}{Td} \right \rfloor \sum_{d'|d} \mu(d')}

注意到最后一个东西实际上是莫反经典柿子，当 d=1 时候才有效。

于是柿子就变成了：

=\prod_{T=1}^{A} T^{\varphi(T)\left \lfloor \frac{C}{T} \right \rfloor \left \lfloor \frac{A}{T} \right \rfloor \left \lfloor \frac{B}{T} \right \rfloor }

这玩意跟分子的第一块约掉了（忘记了就回去康康）。

对于 \frac{d}{d'}：

\prod_{T=1}^{A} (\prod_{d|T} \prod_{d'|d} (\frac{d}{d'})^{\mu(T/d) \times \left \lfloor \frac{C}{d'} \right \rfloor \varphi(d')})^{\left \lfloor \frac{A}{T} \right \rfloor \left \lfloor \frac{B}{T} \right \rfloor }

这里有个更阴间的操作：将 T 和 d 同时乘上 d'。

=\prod_{d'=1}^{A}\prod_{T=1}^{A/d'}\prod_{d|T} d^{\mu(T/d)\varphi(d')\left \lfloor \frac{A}{T} \right \rfloor \left \lfloor \frac{B}{T} \right \rfloor \left \lfloor \frac{C}{d'} \right \rfloor }

你发现其中有个东西是我们之前得到的 f。

=\prod_{T=1}^{A}(\prod_{d=1}^{A/T} f(d)^{\left \lfloor \frac{A}{Td} \right \rfloor \left \lfloor \frac{B}{Td} \right \rfloor })^{\varphi(T)\left \lfloor \frac{C}{T} \right \rfloor }

套两个整除分块，\left \lfloor \frac{A}{T} \right \rfloor 最大到 \sqrt{n}，那么里面的数论分块就是 n^{0.25}

这样就是 O(n^{0.75} \log n)。

整理一下之前的东西。

需要预处理的：

f(T)=\prod_{d|T} d^{\mu(T/d)}

f_2(T)=f(T)^{T^2}

F(T)=\prod_{i=1}^{T}i^i

F_2(T)=(\prod_{i=1}^{T}i)^{\varphi(T)}

sum(T)=\sum_{i=1}^{T} i

fac(T)=T!

接下来与题解无关，单纯是小技巧。

首先回到开头，我们用以下东西来表示：

G(A, B, C)=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} \gcd(i, j)^{f(type)}

H(A,B,C)=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} i ^{f(type)}

那么答案就是：

\frac{H(A,B,C) \times H(B,A,C)}{G(A,B,C) \times G(A,C,B)}

写个函数就可以大大减少码量（虽然我知道是个人都会）。

我们再来梳理一下要求的东西。

H_0(A,B,C)=fac(A)^{B \times C}

G_0(A,B,C)={\large \left ( \prod_{T=1}{\large \left ( {\normalsize f(T} \right ) }^{\left \lfloor \frac{A}{T} \right \rfloor \left \lfloor \frac{B}{T} \right \rfloor } \right ) }^C

H_1(A,B,C)=F(A)^{sum(B) \times sum(C)}

G_1(A,B,C)=(\prod_{T=1}^{A} f_2(T)^{sum(A/T) \times sum(B/T)})^{sum(C)}

H_2(A,B,C)=(\left \lfloor \frac{A}{T} \right \rfloor !)^{\left \lfloor \frac{B}{T} \right \rfloor \left \lfloor \frac{C}{T} \right \rfloor \varphi(T)}

G_2(A,B,C)=\prod_{T=1}^{A}(\prod_{d=1}^{A/T} f(d)^{\left \lfloor \frac{A}{Td} \right \rfloor \left \lfloor \frac{B}{Td} \right \rfloor })^{\varphi(T)\left \lfloor \frac{C}{T} \right \rfloor }

放一下窝的屎山代码。。。。

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
signed P;
inline int read(){
    char ch=getchar();int x=0, f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline int mod(int x, int mos){
    x=(x%mos+mos)%mos;
    return x;
}
inline int ksm(int a, int b, int mos){
    int ret=1;b=mod(b, mos-1);
    for(; b; b>>=1, a=1ll*a*a%mos)
        if(b&1) ret=1ll*ret*a%mos;
    return ret;
}
namespace Solution{
    const int N=1e5+1e3;
    int mu[N], phi[N], u[N], st[N], top;
    int fac[N], f[N], f_inv[N], F[N], f2[N], f2_inv[N];
    void pre(int n){
        fac[0]=1, mu[1]=1, phi[1]=1;
        for(int i=1; i<=n; i++)
            fac[i]=1ll*fac[i-1]*i%P;
        for(int i=2; i<=n; i++){
            if(!u[i]){st[++top]=i, mu[i]=-1, phi[i]=i-1;}
            for(int j=1; j<=top&&1ll*i*st[j]<=n; j++){
                u[i*st[j]]=1;
                if(i%st[j]==0){mu[i*st[j]]=0, phi[i*st[j]]=phi[i]*st[j];break;} 
                mu[i*st[j]]=-mu[i], phi[i*st[j]]=phi[i]*phi[st[j]];
            }
        }
        for(int i=0; i<=n; i++)
            f[i]=f2[i]=1;
        f_inv[0]=f2_inv[0]=1;
        for(int j=1; j<=n; j++)
            if(mu[j]) //小剪枝 
                for(int i=j; i<=n; i+=j)
                    f[i]=1ll*f[i]*ksm(i/j, mu[j], P)%P;
        for(int i=0; i<=n; i++)
            F[i]=ksm(i, i, P),
            f2[i]=ksm(f[i], 1ll*i*i%(P-1), P);
        for(int i=1; i<=n; i++)
            f[i]=1ll*f[i]*f[i-1]%P, f_inv[i]=ksm(f[i], P-2, P),
            f2[i]=1ll*f2[i]*f2[i-1]%P, f2_inv[i]=ksm(f2[i], P-2, P),
            F[i]=1ll*F[i]*F[i-1]%P, phi[i]=mod(phi[i]+phi[i-1], P-1);
//      for(int i=99998; i<=100000; i++)
//          printf(">>>>>>f2[%lld]=%lld\n", i, f2[i]);
        return ;
    }
    int sum(int S, int mos){
        if(S&1) return 1ll*(S+1)/2*S%mos;
        return 1ll*S/2*(S+1)%mos;
    }
    inline int H0(int A, int B, int C){
//  printf("fac[%lld]=%lld\n", A, fac[A]); 
        return ksm(fac[A], B*C%(P-1), P);
    }
    inline int G0(int A, int B, int C){
        int ret=1, t=min(A, B);
        for(int l=1, r; l<=t; l=r+1){
            r=min(A/(A/l), B/(B/l));
            int tmp=1ll*f[r]*f_inv[l-1]%P;
            tmp=ksm(tmp, (A/l)*(B/l)%(P-1), P);
//          if(ret==0) printf("find 0 at %lld\n", l);
            ret=1ll*ret*tmp%P;
        }
        return ksm(ret, C, P);
    }
    inline int H1(int A, int B, int C){
        return ksm(F[A], 1ll*sum(B, P-1)*sum(C, P-1)%(P-1), P);
    }
    inline int G1(int A, int B, int C){
        int ret=1, t=min(A, B);
        for(int l=1, r; l<=t; l=r+1){
            r=min(A/(A/l), B/(B/l));
            int tmp=1ll*f2[r]*f2_inv[l-1]%P;
            tmp=ksm(tmp, 1ll*sum(A/l, P-1)*sum(B/l, P-1)%(P-1), P);
//          if(ret==0) printf("find 0 at %lld\n", l);
            ret=1ll*ret*tmp%P;
        }
        return ksm(ret, sum(C, P-1), P);
    }
    inline int H2(int A, int B, int C){
        int ret=1, t=min(A, min(B, C));
        for(int l=1, r; l<=t; l=r+1){
            r=min(A/(A/l), min(B/(B/l), C/(C/l)));
            int tmp=1ll*(B/l)*(C/l)%(P-1)*mod(phi[r]-phi[l-1], P-1)%(P-1);
            tmp=ksm(fac[A/l], tmp, P);
            ret=1ll*ret*tmp%P;
        }
        return ret;
    }
    int zcfk(int A, int B){
        int ret=1, t=min(A, B);
        for(int l=1, r=0; l<=t; l=r+1){
            r=min(A/(A/l), B/(B/l));
            int tmp=ksm(1ll*f[r]*f_inv[l-1]%P, 1ll*(A/l)*(B/l)%(P-1), P);
            ret=1ll*ret*tmp%P;
        }
//      printf("--%lld\n", ret);
        return ret;
    }
    inline int G2(int A, int B, int C){
        int ret=1, t=min(A, min(B, C));
        for(int l=1, r=0; l<=t; l=r+1){
            r=min(A/(A/l), min(B/(B/l), C/(C/l)));
            int tmp=ksm(zcfk(A/l, B/l), 1ll*mod(phi[r]-phi[l-1], P-1)*(C/l)%(P-1), P);
            ret=1ll*ret*tmp%P;
        }
        return ret;
    }
    int type1(int A, int B, int C){
        int ret=1ll*H0(A, B, C)*H0(B, A, C)%P;
        int rem=1ll*G0(A, B, C)*G0(A, C, B)%P;
        return mod(1ll*ret*ksm(rem, P-2, P)%P, P);
    }
    int type2(int A, int B, int C){
        int ret=1ll*H1(A, B, C)*H1(B, A, C)%P;
        int rem=1ll*G1(A, B, C)*G1(A, C, B)%P;//printf("rem:%lld\n", rem);
        return mod(1ll*ret*ksm(rem, P-2, P)%P, P);
    }
    int type3(int A, int B, int C){
        int ret=1ll*H2(A, B, C)*H2(B, A, C)%P;
        int rem=1ll*G2(A, B, C)*G2(A, C, B)%P;//printf("rem:%lld\n", rem);
        return mod(1ll*ret*ksm(rem, P-2, P)%P, P);
        return 0;
    }
    signed work(){
        int T=read();P=read();
        pre(100000);
//      printf("--%lld %lld\n", fac[99999], fac[99998]);
        for(int i=1; i<=T; i++){
            int A=read(), B=read(), C=read();
            printf("%lld %lld %lld\n", type1(A, B, C), type2(A, B, C), type3(A, B, C));
        }
        return 0;
    }
}

signed main(){
    Solution :: work();
    return 0;
}
/*
1 998244353
99998 99999 100000
99998 100000 99999
99999 99998 100000
99999 100000 99998
100000 99998 99999 
100000 99999 99998  
*/