P5518

发表于 更新于 分类于
[MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题

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

md 果然是 基 础 练 习 题，推完式子就是良心大模拟，外加劲爽卡常。

做这个题不过就是复健一下，没想到差点就残废了（东方题杀我）。。。

三问的关联不大，分开讲吧。

当 $type=0$ 时。

这个问题实际上和 P3704 是一样的（或者说非常类似的）。

这里我就偷懒不写每一步的具体解释了。

$$
\begin{aligned}
Ans&=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\dfrac{\operatorname{lcm}(i,j)}{\gcd(i,k)}
\\
&=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\dfrac{ij}{\gcd(i,j)\gcd(i,k)}
\\
&=(A!)^{BC}(B!)^{AC}\left(\prod_{i=1}^{A}\prod_{j=1}^{B}\dfrac{1}{\gcd(i,j)}\right)^{C}\left(\prod_{i=1}^{A}\prod_{j=1}^{C}\dfrac{1}{\gcd(i,k)}\right)^{B}
\end{aligned}
$$

这个时候我们发现后面的两个因式的结构是相似的，不妨将它们设为一个二元函数的形式：

$$
\begin{aligned}
f(n,m)&=\prod_{i=1}^{n}\prod_{j=1}^{m}\dfrac{1}{\gcd(i,j)}
\\
&=\prod_{d=1}\prod_{i=1}^{n}\prod_{j=1}^{m}\left(\dfrac{1}{d}\right)^{[\gcd(i,j)=d]}
\\
&=\prod_{d=1}\left(\dfrac{1}{d}\right)^{\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]}
\\
&=\prod_{d=1}\left(\dfrac{1}{d}\right)^{\sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor}[\gcd(i,j)=1]}
\\
&=\prod_{d=1}\left(\dfrac{1}{d}\right)^{\sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor}\sum_{k\mid i,k\mid j}\mu(k)}
\\
&=\prod_{d=1}\left(\dfrac{1}{d}\right)^{\sum_{k=1}\mu(k)\lfloor n/(kd)\rfloor\lfloor m/(kd)\rfloor}
\end{aligned}
$$

设 $T=kd$，则 $k=T/d$，于是我们有：

$$
f(n,m)=\prod_{T=1}\left(\prod_{d\mid T}\left(\dfrac{1}{d}\right)^{\mu(T/d)}\right)^{\lfloor n/T\rfloor\lfloor m/T\rfloor}
$$

与 P3704 类似，我们设：

$$
g(n)=\prod_{d\mid n}\left(\dfrac{1}{d}\right)^{\mu(n/d)}
$$

然后我们可以类似埃氏筛的方法在 $O(n\ln n \log p)$ 的复杂度下求出 $g$。

然后设一个前缀乘的函数：

$$
c(n)=\prod_{i=1}^{n}g(i)
$$

然后我们就可以对 $f(n,m)$ 数论分块求解，单次求 $f(n,m)$ 是 $O(\sqrt{n}\log p)$ 的。

这里范围比较小，不用扩展欧拉定理也无所谓。

最后：

$$
Ans=(A!)^{BC}(B!)^{AC}f(A,B)^{C}f(A,C)^{B}
$$

求得第一小问答案的总复杂度是 $O(n\ln n\log p+T\sqrt{n}\log p)$ 的。

当 $type=1$ 时。

实际上和上面的问题差别不大。

$$
\begin{aligned}
Ans&=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\dfrac{\operatorname{lcm}(i,j)}{\gcd(i,k)}\right)^{ijk}
\\
&=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\dfrac{ij}{\gcd(i,j)\gcd(i,k)}\right)^{ijk}
\\
&=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\dfrac{1}{\gcd(i,j)}\right)^{ijk}\left(\dfrac{1}{\gcd(i,k)}\right)^{ijk}(i)^{ijk}(j)^{ijk}
\end{aligned}
$$

看起来会有一大堆等差数列求和，可以提前设：

$$
f(n)=\sum_{i=1}^{n}i=\dfrac{n(n+1)}{2}
$$

然后我们继续变形原式。

$$
\begin{aligned}
Ans=&\left(\prod_{i=1}^{A}(i)^{i}\right)^{f(B)f(C)}\left(\prod_{j=1}^{B}(j)^{j}\right)^{f(A)f(C)}
\\
&\left(\prod_{i=1}^{A}\prod_{j=1}^{B}\left(\dfrac{1}{\gcd(i,j)}\right)^{ij}\right)^{f(C)}
\\
&\left(\prod_{i=1}^{A}\prod_{k=1}^{C}\left(\dfrac{1}{\gcd(i,k)}\right)^{ik}\right)^{f(B)}
\end{aligned}
$$

前面两个因式显然可以 $O(n\log p)$ 预处理，然后单次 $O(\log p)$。当然需要用扩展欧拉定理缩小指数。

后面两项的结构类似，我们同样设函数解决：

$$
\begin{aligned}
g(n,m)&=\prod_{i=1}^{n}\prod_{j=1}^{m}\left(\dfrac{1}{\gcd(i,j)}\right)^{ij}
\\
&=\prod_{d=1}\prod_{i=1}^{n}\prod_{j=1}^{m}\left(\dfrac{1}{d}\right)^{[\gcd(i,j)=d]ij}
\\
&=\prod_{d=1}\left(\dfrac{1}{d}\right)^{\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]ij}
\\
&=\prod_{d=1}\left(\dfrac{1}{d}\right)^{\sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor}[\gcd(i,j)=1]ijd^2}
\\
&=\prod_{d=1}\left(\dfrac{1}{d}\right)^{d^2\sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor}\sum_{k\mid i,k\mid j}ij\mu(k)}
\\
&=\prod_{d=1}\left(\dfrac{1}{d}\right)^{d^2\sum_{k=1}\mu(k)k^2f(\lfloor n/(kd)\rfloor)f(\lfloor m/(kd)\rfloor)}
\\
&=\prod_{k=1}\prod_{d=1}\left(\dfrac{1}{d}\right)^{d^2\mu(k)k^2f(\lfloor n/(kd)\rfloor)f(\lfloor m/(kd)\rfloor)}
\end{aligned}
$$

设 $T=kd$，则 $k=T/d$，于是我们有：

$$
\begin{aligned}
g(n,m)&=\prod_{T=1}\prod_{d\mid T}\left(\dfrac{1}{d}\right)^{d^2(T/d)^2\mu(T/d)f(\lfloor n/T\rfloor)f(\lfloor m/T\rfloor)}
\\
&=\prod_{T=1}\left(\prod_{d\mid T}\left(\dfrac{1}{d}\right)^{\mu(T/d)T^2}\right)^{f(\lfloor n/T\rfloor)f(\lfloor m/T\rfloor)}
\end{aligned}
$$

中间那一坨东西类似 $type=0$ 时候的 $g$ 函数，同样需要预处理。

然后我们单次求 $g(n,m)$ 是 $O(\sqrt{n}\log p)$ 的。同样需要用扩展欧拉定理降低指数。

最后我们的答案就是：

$$Ans=\left(\prod_{i=1}^{A}(i)^{i}\right)^{f(B)f(C)}\left(\prod_{j=1}^{B}(j)^{j}\right)^{f(A)f(C)}g(A,B)^{f(C)}g(A,C)^{f(B)}$$

最后求得第二小问答案的总复杂度是 $O(n\ln n\log p+T\sqrt{n}\log p)$ 的。

当 $type=2$ 时。

这个是最恶心的小问。

$$
\begin{aligned}
Ans=& \prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\dfrac{ij}{\gcd(i,j)\gcd(i,k)}\right)^{\gcd(i,j,k)}
\\
=& \prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\prod_{d\mid i,d\mid j,d\mid k}\left(\dfrac{ij}{\gcd(i,j)\gcd(i,k)}\right)^{\varphi(d)}
\\
=& \prod_{d=1}\prod_{i=1}^{\lfloor A/d\rfloor}\prod_{j=1}^{\lfloor B/d\rfloor}\prod_{k=1}^{\lfloor C/d\rfloor}\left(\dfrac{ij}{\gcd(i,j)\gcd(i,k)}\right)^{\varphi(d)}
\\
=&\left(\prod_{d=1}\prod_{i=1}^{\lfloor A/d\rfloor}\prod_{j=1}^{\lfloor B/d\rfloor}\prod_{k=1}^{\lfloor C/d\rfloor}\left(i\right)^{\varphi(d)}\right)
\\
& \left(\prod_{d=1}\prod_{i=1}^{\lfloor A/d\rfloor}\prod_{j=1}^{\lfloor B/d\rfloor}\prod_{k=1}^{\lfloor C/d\rfloor}\left(j\right)^{\varphi(d)}\right)
\\
& \left(\prod_{d=1}\prod_{i=1}^{\lfloor A/d\rfloor}\prod_{j=1}^{\lfloor B/d\rfloor}\prod_{k=1}^{\lfloor C/d\rfloor}\left(\dfrac{1}{\gcd(i,j)}\right)^{\varphi(d)}\right)
\\
& \left(\prod_{d=1}\prod_{i=1}^{\lfloor A/d\rfloor}\prod_{j=1}^{\lfloor B/d\rfloor}\prod_{k=1}^{\lfloor C/d\rfloor}\left(\dfrac{1}{\gcd(i,k)}\right)^{\varphi(d)}\right)
\end{aligned}
$$

前面两个因式的结构相同，设函数：

$$
\begin{aligned}
f(a,b,c)=& \prod_{d=1}\prod_{i=1}^{\lfloor a/d\rfloor}\prod_{j=1}^{\lfloor b/d\rfloor}\prod_{k=1}^{\lfloor c/d\rfloor}\left(i\right)^{\varphi(d)}
\\
=& \prod_{d=1}\left(\prod_{i=1}^{\lfloor a/d\rfloor}i\right)^{\varphi(d)\lfloor b/d\rfloor\lfloor c/d\rfloor}
\\
=& \prod_{d=1}\left(\left\lfloor \dfrac{a}{d}\right\rfloor!\right)^{\varphi(d)\lfloor b/d\rfloor\lfloor c/d\rfloor}
\end{aligned}
$$

三维数论分块就完了，时间复杂度 $O(\sqrt{n}\log n)$。

然后看答案的后面两个因式：

$$
\begin{aligned}
g(a,b,c)=& \prod_{d=1}\prod_{i=1}^{\lfloor a/d\rfloor}\prod_{j=1}^{\lfloor b/d\rfloor}\prod_{k=1}^{\lfloor c/d\rfloor}\left(\dfrac{1}{\gcd(i,j)}\right)^{\varphi(d)}
\\
=& \prod_{d=1}\left(\prod_{i=1}^{\lfloor a/d\rfloor}\prod_{j=1}^{\lfloor b/d\rfloor}\left(\dfrac{1}{\gcd(i,j)}\right)\right)^{\lfloor c/d\rfloor\varphi(d)}
\end{aligned}
$$

同样是三维数论分块，把中间的一坨东西搞出来，于是我们设：

$$
\begin{aligned}
h(n,m)=&\prod_{i=1}^{n}\prod_{j=1}^{m}\left(\dfrac{1}{\gcd(i,j)}\right)
\\
=&\prod_{d=1}\prod_{i=1}^{\lfloor n/d\rfloor}\prod_{j=1}^{\lfloor m/d\rfloor}\left(\dfrac{1}{d}\right)^{[\gcd(i,j)=1]}
\\
=& \prod_{d=1}\prod_{i=1}^{\lfloor n/d\rfloor}\prod_{j=1}^{\lfloor m/d\rfloor}\left(\dfrac{1}{d}\right)^{\sum_{k\mid i,k\mid j}\mu(k)}
\\
=& \prod_{d=1}\prod_{k=1}\left(\dfrac{1}{d}\right)^{\mu(k)\lfloor n/(kd)\rfloor\lfloor m/(kd)\rfloor}
\end{aligned}
$$

设 $T=kd$，则 $k=T/d$：

$$
\begin{aligned}
h(n,m)=&\prod_{T=1}\left(\prod_{d|T}\left(\dfrac{1}{d}\right)^{\mu(T/d)}\right)^{\lfloor n/T\rfloor\lfloor m/T\rfloor}
\end{aligned}
$$

中间那个东西我们显然在前两问已经预处理过了，直接拿过来用就完了。后面的指数同样数论分块掉。

然后我们这个是数论分块套数论分块，复杂度分析类似于不加预处理的杜教筛：

$$
\begin{aligned}
T(n)=& O\left(\sum_{i=1}^{\sqrt{n}}\sqrt{i}+\sum_{i=1}^{\sqrt{n}}\sqrt{\left\lfloor\dfrac{n}{i}\right\rfloor}\right)
\\
=& O\left(\int_{1}^{\sqrt{n}}x^{1/2}\,\delta x+\int_{1}^{\sqrt{n}}\sqrt{\dfrac{n}{x}}\,\delta x\right)
\\
=& O\left(\dfrac{2}{3}n^{3/4}-\dfrac{2}{3}+2n^{3/4}-2n^{1/2}\right)
\\
=& O(n^{3/4})
\end{aligned}
$$

于是我们的答案就是：

$$
Ans=f(A,B,C)f(B,A,C)g(A,B,C)g(A,C,B)
$$

四舍五入单次计算答案就是 $O(n^{3/4}\log n)$ 的。

总的复杂度就是 $O(Tn^{3/4}\log n)$。

至此，三小问全部解决，问题以 $O(n\sqrt{n}+n\ln n\log p+Tn^{3/4}\log p)$ 的复杂度解决。

代码真的很难写。。。要预处理的东西和各小问之间的函数实在是太乱了，字母真的已经在乱标了。。。

再加上本题卡常非常劲爽，整整交了有 3 页左右（浪费评测资源实锤）。。。

一个比较劲爆的卡常技巧：把一些已经预处理出的数的逆元提前求出，避免重复快速幂，速度飞升。

然后我用的还有一些用处不大的卡常，比如把 __int128 换成 long long（但是该强制转换还是要换，不然指数会溢出），先判断后取余，记忆化。。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include<iostream>
#include<cstdio>
#include<map>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writes(ll x) {write(x);putchar(32);}
inline void writeln(ll x) {write(x);putchar(10);}
inline ll Fm(__int128 x,__int128 y) {if(x>=y) return x%y;return x;}

const ll N=1e5;

ll mo,cnt;
ll phi[N+5],mu[N+5],prime[N+5];
ll fac[N+5],g0[N+5],c0[N+5],ff1[N+5],sphi[N+5],cc1[N+5],gg1[N+5];
ll invc0[N+5],invcc1[N+5];
bool f[N+5];
map<ll,ll> rem[N+5];

inline ll Pow(ll b,__int128 p) {
  if(b==1) return 1;if(b==0) return 0;
  if(p>mo-1) p=Fm(p,mo-1)+mo-1;b=Fm(b,mo);
  ll r=1;while(p) {if(p&1) r=Fm(r*b,mo);b=Fm(b*b,mo);p>>=1;}return r;
}

inline ll f0(ll a,ll b) {
  ll r=1;
  for(ll i=1,j;i<=a&&i<=b;i=j+1) {
    ll tmp1=a/i,tmp2=b/i;
    j=min(a/tmp1,b/tmp2);
    r=Fm(r*Pow(Fm(c0[j]*invc0[i-1],mo)
    ,(__int128)tmp1*(__int128)tmp2),mo);
  }
  return r;
}

inline ll f1(ll x) {return (x*(x+1))>>1;}

inline ll g1(ll n,ll m) {
  ll r=1;
  for(ll i=1,j;i<=n&&i<=m;i=j+1) {
    ll tmp1=n/i,tmp2=m/i;
    j=min(n/(n/i),m/(m/i));
    r=Fm(r*Pow(Fm(cc1[j]*invcc1[i-1],mo)
    ,(__int128)f1(tmp1)*(__int128)f1(tmp2)),mo);
  }
  return r;
}

inline ll f2(ll a,ll b,ll c) {
  ll r=1;
  for(ll i=1,j;i<=a&&i<=b&&i<=c;i=j+1) {
    ll tmp1=a/i,tmp2=b/i,tmp3=c/i;
    j=min(a/tmp1,min(b/tmp2,c/tmp3));
    r=Fm(r*Pow(fac[tmp1]
    ,(__int128)(sphi[j]-sphi[i-1])*(__int128)tmp2*(__int128)tmp3),mo);
  }
  return r;
}

inline ll h2(ll n,ll m) {
  if(rem[n].find(m)!=rem[n].end()) return rem[n][m];
  if(rem[m].find(n)!=rem[m].end()) return rem[m][n];
  ll r=1;
  for(ll i=1,j;i<=n&&i<=m;i=j+1) {
    ll tmp1=n/i,tmp2=m/i;
    j=min(n/tmp1,m/tmp2);
    r=Fm(r*Pow(Fm(c0[j]*invc0[i-1],mo)
    ,(__int128)tmp1*(__int128)tmp2),mo);
  }
  return rem[m][n]=rem[n][m]=r;
}

inline ll g2(ll a,ll b,ll c) {
  ll r=1;
  for(ll i=1,j;i<=a&&i<=b&&i<=c;i=j+1) {
    ll tmp1=a/i,tmp2=b/i,tmp3=c/i;
    j=min(a/tmp1,min(b/tmp2,c/tmp3));
    r=Fm(r*Pow(Fm(h2(tmp1,tmp2),mo)
    ,(__int128)(sphi[j]-sphi[i-1])*(__int128)tmp3),mo);
  }
  return r;
}

inline void Init() {
  f[1]=1;phi[1]=1;mu[1]=1;
  for(ll i=2;i<=N;i++) {
    if(!f[i]) {prime[++cnt]=i;phi[i]=i-1;mu[i]=-1;}
    for(ll j=1;j<=cnt&&prime[j]*i<=N;j++) {
      f[i*prime[j]]=1;
      if(i%prime[j]==0) {
        phi[i*prime[j]]=phi[i]*prime[j];mu[i*prime[j]]=0;
        break;
      }
      phi[i*prime[j]]=phi[i]*(prime[j]-1);mu[i*prime[j]]=-mu[i];
    }
  }
  for(ll i=1;i<=N;i++) sphi[i]=sphi[i-1]+phi[i];
  fac[0]=1;for(ll i=1;i<=N;i++) {fac[i]=Fm(fac[i-1]*i,mo);}
  ff1[0]=1;for(ll i=1;i<=N;i++) {ff1[i]=Fm(ff1[i-1]*Pow(i,i),mo);}
  for(ll i=1;i<=N;i++) {g0[i]=1;}
  for(ll i=1;i<=N;i++) {
    ll tmp=Pow(i,mo-2);
    for(ll j=i,t=1;j<=N;j+=i,t++) {
      if(mu[t]==0) continue;
      if(mu[t]==1) g0[j]=Fm(g0[j]*tmp,mo);
      if(mu[t]==-1) g0[j]=Fm(g0[j]*i,mo);
    }
  }
  c0[0]=1;invc0[0]=1;
  for(ll i=1;i<=N;i++) {
    c0[i]=Fm(c0[i-1]*g0[i],mo);
    invc0[i]=Pow(c0[i],mo-2);
  }
  for(ll i=1;i<=N;i++) {gg1[i]=1;}
  for(ll i=1;i<=N;i++) {
    ll tmp=Pow(i,mo-2);
    for(ll j=i,t=1;j<=N;j+=i,t++) {
      if(mu[t]==0) continue;
      if(mu[t]==1) gg1[j]=Fm(gg1[j]*Pow(tmp,j*j),mo);
      if(mu[t]==-1) gg1[j]=Fm(gg1[j]*Pow(i,j*j),mo);
    }
  }
  cc1[0]=1;invcc1[0]=1;
  for(ll i=1;i<=N;i++) {
    cc1[i]=Fm(cc1[i-1]*gg1[i],mo);
    invcc1[i]=Pow(cc1[i],mo-2);
  }
}

int main() {
  
  ll T;
  T=read();mo=read();Init();
  
  while(T--) {
    ll A,B,C;
    A=read();B=read();C=read();
    ll ans1=0;
    ans1=Fm(Pow(fac[A],B*C)*Pow(fac[B],A*C),mo);
    ans1=Fm(ans1*Pow(f0(A,B),C),mo);
    ans1=Fm(ans1*Pow(f0(A,C),B),mo);
    writes(ans1);
    ll ans2=0;
    ans2=Fm(Pow(ff1[A],(__int128)f1(B)*f1(C)),mo);
    ans2=Fm(ans2*Pow(ff1[B],(__int128)f1(A)*f1(C)),mo);
    ans2=Fm(ans2*Pow(g1(A,B),f1(C)),mo);
    ans2=Fm(ans2*Pow(g1(A,C),f1(B)),mo);
    writes(ans2);
    ll ans3=0;
    ans3=f2(A,B,C);
    ans3=Fm(ans3*f2(B,A,C),mo);
    ans3=Fm(ans3*g2(A,B,C),mo);
    ans3=Fm(ans3*g2(A,C,B),mo);
    writeln(ans3);
  }
  
  return 0;
}