P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题
木xx木大
·
·
题解
P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题
基础练习题都是毒瘤阴间题！
写这题之前我从来没想过莫反题码量能有 4k 。。。
type=0：
\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^C{\left(\frac{ij}{\gcd(i,j)\gcd(i,k)}\right)}\\=(A!)^{BC}(B!)^{AC}\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{-C}\times\prod_{i=1}^A\prod_{j=1}^C\gcd(i,k)^{-B}
前两部分（分子）直接预处理阶乘+快速幂，后半部分为：
\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^C\\(枚举\gcd)=\prod_{d=1}^{\min(A,B)}\prod_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\prod_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}d^{C[\gcd(i,j)=1]}\\(把i,j放到指数上)=\prod_{d=1}^{\min(A,B)}d^{\sum\limits_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}C[\gcd(i,j)=1]}\\(按套路反演)=\prod_{d=1}^{\min(A,B)}d^{{C\sum\limits_{p=1}^{\min(\left\lfloor\frac{A}{d}\right\rfloor,\left\lfloor\frac{B}{d}\right\rfloor)}}\left\lfloor\frac{A}{pd}\right\rfloor\left\lfloor\frac{B}{pd}\right\rfloor\mu(p)}
预处理 \mu 的前缀和，然后整除分块套整除分块即可。
type=1：
\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^C{\left(\frac{ij}{\gcd(i,j)\gcd(i,k)}\right)}^{ijk}\\
=\prod_{i=1}^Ai^{i\sum\limits_{j=1}^Bj\sum\limits_{k=1}^Ck}\prod_{j=1}^Bj^{j\sum\limits_{i=1}^Ai\sum\limits_{k=1}^Ck}\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^{C}\gcd(i,j)^{-ijk}\times\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^{C}\gcd(i,k)^{-ijk}
前半部分（分子）为
\prod_{i=1}^A (i^i)^{B(B+1)C(C+1)/4}
预处理 i^i 的前缀积就可以直接算了。
设 D=C(C+1)/2 ，后半部分（分母）为
\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{ijD}\\(枚举\gcd)=\prod_{d=1}^{\min(A,B)}\prod_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\prod_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}d^{d^2ijD[\gcd(i,j)=1]} \\(把i,j放到指数上)=\prod_{d=1}^{\min(A,B)}d^{\sum\limits_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}Dijd^2[\gcd(i,j)=1]} \\(向上面那样按套路反演)=\prod_{d=1}^{\min(A,B)}d^{{D\sum\limits_{p=1}^{\min(\left\lfloor\frac{A}{d}\right\rfloor,\left\lfloor\frac{B}{d}\right\rfloor)}}\sum\limits_{i=1}^{\left\lfloor\frac{A}{pd}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{B}{pd}\right\rfloor}d^2p^2ij \mu(p)}\\=(\prod_{d=1}^{\min(A,B)}d^{d^2})^{D\sum\limits_{p=1}^{\min(\left\lfloor\frac{A}{d}\right\rfloor,\left\lfloor\frac{B}{d}\right\rfloor)}p^2\mu(p)\frac{\left\lfloor\frac{A}{dp}\right\rfloor(\left\lfloor\frac{A}{dp}\right\rfloor+1)}{2}\frac{\left\lfloor\frac{B}{dp}\right\rfloor(\left\lfloor\frac{B}{dp}\right\rfloor+1)}{2}}
预处理 d^{d^2} 的前缀积，预处理 p^2 \mu(p) 的前缀和然后整除分块套整除分块即可。
type=2（重头戏来了！）
\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^C{\left(\frac{ij}{\gcd(i,j)\gcd(i,k)}\right)}^{\gcd(i,j,k)}
\\=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^Ci^{\gcd(i,j,k)}\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^Cj^{\gcd(i,j,k)}\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^{C}\gcd(i,j)^{-\gcd(i,j,k)}\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^{C}\gcd(i,k)^{-\gcd(i,j,k)}
前半部分（分子）为
后半部分：
\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^{C}\gcd(i,j)^{\gcd(i,j,k)}\\(把i,j放指数上并枚举\gcd)=\prod_{d=1}^{\min(A,B)}d^{\sum\limits_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}[\gcd(i,j)=1]\sum\limits_{k=1}^C\gcd(d,k)}\\(按套路反演)=\prod_{d=1}^{\min(A,B)}d^{\sum\limits_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}\sum\limits_{t|i,t|j}\mu(t)\sum\limits_{k=1}^C\gcd(d,k)}\\(化简)=\prod_{d=1}^{\min(A,B)}d^{\sum\limits_{t=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\mu(t){\left\lfloor\frac{A}{td}\right\rfloor}{\left\lfloor\frac{B}{td}\right\rfloor}\sum\limits_{k=1}^C\gcd(d,k)}\\(设T=dt)=\prod_{T=1}^{\min(A,B)}\prod_{d|T}d^{\mu(\frac{T}{d}){\left\lfloor\frac{A}{T}\right\rfloor}{\left\lfloor\frac{B}{T}\right\rfloor}\sum\limits_{k=1}^C\gcd(d,k)}\\(把式子写好看一点)=\prod_{T=1}^{\min(A,B)}{\left(\prod_{d|T}d^{\mu(\frac{T}{d})\sum\limits_{k=1}^C\gcd(d,k)}\right)^{{\left\lfloor\frac{A}{T}\right\rfloor}{\left\lfloor\frac{B}{T}\right\rfloor}}}
把中间的指数部分提出来
\sum\limits_{k=1}^C\gcd(d,k)\\
=\sum\limits_{p|d}p\sum\limits_{k=1}^{\left\lfloor\frac{C}{p}\right\rfloor}[\gcd(\frac{C}{d},k)=1]
\\=\sum\limits_{p|d}p\sum\limits_{t|\frac{d}{p}}\mu(t){\left\lfloor\frac{C}{pt}\right\rfloor}\\
=\sum\limits_{s|d}{\left\lfloor\frac{C}{s}\right\rfloor\phi(s)}
再扔回去
\prod_{T=1}^{\min(A,B)}{\left(\prod_{d|T}d^{\mu(\frac{T}{d})\sum\limits_{s|d}{\left\lfloor\frac{C}{s}\right\rfloor\phi(s)}}\right)^{{\left\lfloor\frac{A}{T}\right\rfloor}{\left\lfloor\frac{B}{T}\right\rfloor}}}\\(把枚举s放下面)=\prod_{T=1}^{\min(A,B)}{\left(\prod_{d|T}\prod\limits_{s|d}d^{\mu(\frac{T}{d}){\left\lfloor\frac{C}{s}\right\rfloor\phi(s)}}\right)^{{\left\lfloor\frac{A}{T}\right\rfloor}{\left\lfloor\frac{B}{T}\right\rfloor}}}
发现仍然不好算，orz题解后发现可以把 s 和 \frac{d}{s} 分开算。
\prod_{T=1}^{\min(A,B)}{{\prod_{d|T}\prod\limits_{s|d}\frac{d}{s}^{\mu(\frac{T}{d})\phi(s)\left\lfloor\frac{C}{s}\right\rfloor\left\lfloor\frac{A}{T}\right\rfloor\left\lfloor\frac{B}{T}\right\rfloor}}}\\(交换枚举顺序，T\div s,d\div s)=\prod_{s=1}^{\min(A,B)}\prod_{T=1}^{\left\lfloor\frac{\min(A,B)}{s}\right\rfloor}{{\prod_{d|T}d^{\mu(\frac{T}{d})\phi(s)\left\lfloor\frac{C}{s}\right\rfloor\left\lfloor\frac{A}{Ts}\right\rfloor\left\lfloor\frac{B}{Ts}\right\rfloor}}}\\(最后整理一下)=\prod_{s=1}^{\min(A,B)}\left(\prod_{T=1}^{\left\lfloor\frac{\min(A,B)}{s}\right\rfloor}{\left({\prod_{d|T}d^{\mu(\frac{T}{d})}}\right)}^{\left\lfloor\frac{\left\lfloor\frac{A}{T}\right\rfloor}{s}\right\rfloor\left\lfloor\frac{\left\lfloor\frac{B}{T}\right\rfloor}{s}\right\rfloor}\right)^{\phi(s)\left\lfloor\frac{C}{s}\right\rfloor}
最里面一层 O(n\log n) 预处理，外面两层整除分块即可。（和上面反演的方法基本一样，就不写注释了）
\prod_{T=1}^{\min(A,B)}{{\prod_{d|T}\prod\limits_{s|d}s^{\mu(\frac{T}{d})\phi(s)\left\lfloor\frac{C}{s}\right\rfloor\left\lfloor\frac{A}{T}\right\rfloor\left\lfloor\frac{B}{T}\right\rfloor}}}
\\=\prod_{s=1}^{\min(A,B)}\prod_{T=1}^{\left\lfloor\frac{\min(A,B)}{s}\right\rfloor}\prod\limits_{d|T}s^{\mu(\frac{T}{d})\phi(s)\left\lfloor\frac{C}{s}\right\rfloor\left\lfloor\frac{A}{Ts}\right\rfloor\left\lfloor\frac{B}{Ts}\right\rfloor}
\\=\prod_{s=1}^{\min(A,B)}s^{\sum\limits_{T=1}^{\left\lfloor\frac{\min(A,B)}{s}\right\rfloor}\sum\limits_{d|T}\mu(\frac{T}{d})\phi(s)\left\lfloor\frac{C}{s}\right\rfloor\left\lfloor\frac{A}{Ts}\right\rfloor\left\lfloor\frac{B}{Ts}\right\rfloor}
\\=\prod_{s=1}^{\min(A,B)}s^{\phi(s)\left\lfloor\frac{C}{s}\right\rfloor\sum\limits_{T=1}^{\left\lfloor\frac{\min(A,B)}{s}\right\rfloor}\left\lfloor\frac{A}{Ts}\right\rfloor\left\lfloor\frac{B}{Ts}\right\rfloor\sum\limits_{d|T}\mu(\frac{T}{d})}
\\=\prod_{s=1}^{\min(A,B)}s^{\phi(s)\left\lfloor\frac{C}{s}\right\rfloor\sum\limits_{T=1}^{\left\lfloor\frac{\min(A,B)}{s}\right\rfloor}\left\lfloor\frac{A}{Ts}\right\rfloor\left\lfloor\frac{B}{Ts}\right\rfloor\epsilon(T)}
因为 \epsilon(T)=[T=1] ，所以可以直接把 T 看作 1，那么
\prod_{s=1}^{\min(A,B)}s^{\phi(s)\left\lfloor\frac{C}{s}\right\rfloor\sum\limits_{T=1}^{\left\lfloor\frac{\min(A,B)}{s}\right\rfloor}\left\lfloor\frac{A}{Ts}\right\rfloor\left\lfloor\frac{B}{Ts}\right\rfloor\epsilon(T)}
\\=\prod_{s=1}^{\min(A,B)}s^{\phi(s)\left\lfloor\frac{C}{s}\right\rfloor\left\lfloor\frac{A}{s}\right\rfloor\left\lfloor\frac{B}{s}\right\rfloor}
终于出现了一个漂亮的式子啊！然后我震惊地发现，这个部分和分子的 \prod_{T=1}^{A}\left(T^{\phi(T)}\right)^{\left\lfloor\frac{A}{T}\right\rfloor\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor} 部分可以约掉！所以我们实际要算的分子是
\prod_{T=1}^{A}(\left\lfloor\frac{A}{T}\right\rfloor!)^{\phi(T){\left\lfloor\frac{B}{T}\right\rfloor}{\left\lfloor\frac{C}{T}\right\rfloor}}
分母是
\prod_{s=1}^{\min(A,B)}\left(\prod_{T=1}^{\left\lfloor\frac{\min(A,B)}{s}\right\rfloor}
{\left({\prod_{d|T}d^{\mu(\frac{T}{d})}}\right)}^
{\left\lfloor\frac{\left\lfloor\frac{A}{T}\right\rfloor}{s}\right\rfloor
\left\lfloor\frac{\left\lfloor\frac{B}{T}\right\rfloor}{s}\right\rfloor}
\right)^{\phi(s)\left\lfloor\frac{C}{s}\right\rfloor}
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
namespace FGF
{
int n,mo,phi;
const int N=1e5+5;
ll A,B,C,fac[N],mu[N],inv[N],dd2[N],p2[N],dd[N],sumphi[N],ph[N],h[N],ifac[N];
ll ih[N];
int p[N],vis[N],cnt;
ll qpow(ll x,ll y)
{
ll s=1;
while(y)
{
if(y&1)s=s*x%mo;
x=x*x%mo,y>>=1;
}
return s;
}
void init()
{
ih[0]=ifac[0]=h[0]=dd[0]=dd2[0]=fac[0]=inv[0]=inv[1]=1;
for(int i=1;i<=1e5;i++)
fac[i]=fac[i-1]*i%mo,h[i]=1;
for(int i=2;i<=1e5;i++)
inv[i]=inv[mo%i]*(mo-mo/i)%mo;
for(int i=1;i<=1e5;i++)
ifac[i]=ifac[i-1]*inv[i]%mo;
for(int i=1;i<=1e5;i++)
dd2[i]=dd2[i-1]*qpow(i,1LL*i*i%phi)%mo;
for(int i=1;i<=1e5;i++)
dd[i]=dd[i-1]*qpow(i,i)%mo;
mu[1]=1,ph[1]=1;
for(int i=2;i<=1e5;i++)
{
if(!vis[i])p[++cnt]=i,mu[i]=phi-1,ph[i]=i-1;
for(int j=1;j<=cnt&&p[j]*i<=1e5;j++)
{
vis[i*p[j]]=1;
if(i%p[j]==0){mu[i*p[j]]=0;ph[i*p[j]]=ph[i]*p[j];break;}
mu[i*p[j]]=phi-mu[i],ph[i*p[j]]=ph[i]*(p[j]-1);
}
}
for(int i=1;i<=1e5;i++)
sumphi[i]=(sumphi[i-1]+ph[i])%phi;
for(int i=1;i<=1e5;i++)
p2[i]=(p2[i-1]+1LL*i*i%phi*mu[i]%phi)%(mo-1);
for(int i=1;i<=1e5;i++)
for(int j=i;j<=1e5;j+=i)
if(mu[j/i]==1)h[j]=h[j]*i%mo;
else if(mu[j/i]==phi-1)h[j]=h[j]*inv[i]%mo;
for(int i=1;i<=1e5;i++)
h[i]=h[i-1]*h[i]%mo,ih[i]=qpow(h[i],mo-2);
for(int i=2;i<=1e5;i++)mu[i]=(mu[i]+mu[i-1])%phi;
}
ll getans1(ll a,ll b,ll c)
{
ll ans=1;
for(int l=1,r;l<=min(a,b);l=r+1)
{
ll d=a/l,e=b/l;
r=min(a/d,b/e);
ll p=fac[r]*ifac[l-1]%mo,sum=0;
for(int ql=1,qr;ql<=min(d,e);ql=qr+1)
{
qr=min(d/(d/ql),e/(e/ql));
ll k=(mu[qr]-mu[ql-1]+phi)%phi;
sum=(sum+k*(d/ql)%phi*(e/ql)%phi)%phi;
}
ans=ans*qpow(qpow(p,sum*c%phi),mo-2)%mo;
}
return ans;
}
ll solve1(ll a,ll b,ll c)
{
ll ans=qpow(fac[a],b*c%(mo-1))*qpow(fac[b],a*c%(mo-1))%mo;
return ans*getans1(a,b,c)%mo*getans1(a,c,b)%mo;
}
ll getans2(ll a,ll b,ll c)
{
ll D=c*(c+1)/2%phi,ans=1;
for(int l=1,r;l<=min(a,b);l=r+1)
{
ll d=a/l,e=b/l;
r=min(a/d,b/e);
ll p=dd2[r]*qpow(dd2[l-1],mo-2)%mo,sum=0;
for(int ql=1,qr;ql<=min(d,e);ql=qr+1)
{
ll g=d/ql,f=e/ql;
qr=min(d/g,e/f);
ll k=(p2[qr]-p2[ql-1]+phi)%phi;
sum=(sum+(g*(g+1)/2%phi)%phi*(f*(f+1)/2%phi)%phi*k%phi)%phi;
}
ans=ans*qpow(qpow(p,sum*D%phi),mo-2)%mo;
}
return ans;
}
ll solve2(ll a,ll b,ll c)
{
ll ans=qpow(dd[a],(b*(b+1)/2%phi)%phi*(c*(c+1)/2%phi)%phi)*qpow(dd[b],(a*(a+1)/2%phi)%phi*(c*(c+1)/2%phi)%phi)%mo;
return ans*getans2(a,b,c)%mo*getans2(a,c,b)%mo;
}
ll getans31(ll a,ll b,ll c)
{
ll s=1;
for(int l=1,r;l<=min(a,min(b,c));l=r+1)
{
r=min(a/(a/l),min(b/(b/l),c/(c/l)));
s=s*qpow(fac[a/l],(sumphi[r]-sumphi[l-1]+phi)%phi*(b/l)%phi*(c/l)%phi)%mo;
}
return s;
}
ll getans32(ll a,ll b,ll c)
{
ll ans=1;
for(int l=1,r;l<=min(a,min(b,c));l=r+1)
{
ll d=a/l,e=b/l,sum=1;
r=min(a/d,min(b/e,c/(c/l)));
for(int ql=1,qr;ql<=min(d,e);ql=qr+1)
{
qr=min(d/(d/ql),e/(e/ql));
sum=sum*qpow(h[qr]*ih[ql-1]%mo,(d/ql)*(e/ql)%phi)%mo;
}
ans=ans*qpow(sum,(sumphi[r]-sumphi[l-1]+phi)%phi*(c/l)%phi)%mo;
}
return ans;
}
ll solve3(ll a,ll b,ll c)
{
return getans31(a,b,c)*getans31(b,a,c)%mo*qpow(getans32(a,b,c),mo-2)%mo*qpow(getans32(a,c,b),mo-2)%mo;
}
void work()
{
scanf("%d%d",&n,&mo),phi=mo-1;
init();
while(n--)
{
scanf("%lld%lld%lld",&A,&B,&C);
printf("%lld %lld %lld \n",solve1(A,B,C),solve2(A,B,C),solve3(A,B,C));
}
}
}
int main()
{
FGF::work();
return 0;
}
顺便放一下，机房巨佬用另一种做法推出来的式子是，我也不知道这玩意能不能算。
\large\prod_{t=1}^{\min(A,B,C)}\prod\limits_{s=1}^{\min(\left\lfloor\frac{\min(A,B)}{t}\right\rfloor,\left\lfloor\frac{C}{t}\right\rfloor)}\prod_{d=1}^{\left\lfloor\frac{\min(A,B)}{ts}\right\rfloor}(dts)^{\left\lfloor\frac{C}{ts}\right\rfloor t\mu(s)\sum\limits_{p=1}^{\min(\left\lfloor\frac{A}{dts}\right\rfloor,\left\lfloor\frac{B}{dts}\right\rfloor)}\left\lfloor\frac{A}{dpts}\right\rfloor \left\lfloor\frac{B}{dpts}\right\rfloor \mu(p)}