【LOJ3284】「USACO 2020 US Open Platinum」Exercise（容斥）

傳送門

題解：

由于最後求的是所有lcm的乘積，直接分質數考慮即可。

假設求出 p p p 的最大次數恰好為 e e e 的置換有 g ( p , e ) g(p,e) g(p,e) 個，顯然對答案的貢獻為 ( p e ) g ( p , e ) (p^e)^{g(p,e)} (pe)g(p,e) ，并不顯然。

我們考慮計算出 p p p 的次數至少為 e e e 的數量，記為 f ( p , e ) f(p,e) f(p,e)，然後計算 ∑ e = 1 f ( p , e ) \sum_{e=1}f(p,e) ∑e=1​f(p,e) 即為答案中 p p p 的次數。

利用 min-max 容斥，我們可以比較輕松地得到一個DP，設 t = p e t=p^e t=pe， f i f_i fi​ 表示總長為 i t it it 的置換，每段長度都是 t t t 的倍數，帶上容斥系數的方案數，轉移枚舉 1 1 1 所在的環長。

f i = − ∑ j = 1 i f i − j ( i t − 1 j t − 1 ) ( j t − 1 ) ! f_i=-\sum_{j=1}^if_{i-j}{it-1\choose jt-1}(jt-1)! fi​=−j=1∑i​fi−j​(jt−1it−1​)(jt−1)!

對于 f ( p , e ) f(p,e) f(p,e) ，有 f ( p , e ) = ∑ i = 1 n / t f i ( n i t ) ( n − i t ) ! f(p,e)=\sum_{i=1}^{n/t}f_i{n\choose it}(n-it)! f(p,e)=i=1∑n/t​fi​(itn​)(n−it)!

注意這裡算的是 p p p 的指數，應該對 M − 1 M-1 M−1 取模。

代碼：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

using std::cerr;
using std::cout;

int phi;
inline int add(int a,int b){return a+b>=phi?a+b-phi:a+b;}
inline int dec(int a,int b){return a-b<0?a-b+phi:a-b;}
inline void Inc(int &a,int b){a+=b-phi;a+=a>>31&phi;}
inline void Dec(int &a,int b){a-=b;a+=a>>31&phi;}
inline int mul(int a,int b){return (ll)a*b%phi;}
int mod;
inline int po(int a,int b){
	int r=1;for(;b;b>>=1,a=(ll)a*a%mod)
	if(b&1)r=(ll)r*a%mod;return r;
}

cs int N=7500+7;

int n,f[N],ans=1;
int C[N][N],fac[N];
int p[N],pc,mrk[N];

void init_math(){
	for(int re i=0;i<=n;++i){
		C[i][0]=1;
		for(int re j=1;j<=i;++j)
			C[i][j]=add(C[i-1][j],C[i-1][j-1]);
	}for(int re i=fac[0]=1;i<=n;++i)
		fac[i]=mul(fac[i-1],i);
	for(int re i=2;i<=n;++i)
		if(!mrk[i]){
			p[++pc]=i;
			for(int re j=i*i;j<=n;j+=i)
				mrk[j]=true;
		}
}

void Main(){
	scanf("%d%d",&n,&mod);
	phi=mod-1;init_math();
	for(int re o=1;o<=pc;++o){
		int ord=0,p=::p[o];
		for(int re t=p;t<=n;t*=p){
			memset(f,0,sizeof(int)*(n/t+3));f[0]=phi-1;
			for(int re i=1;i*t<=n;++i)
				for(int re j=1;j<=i;++j)
					Dec(f[i],mul(mul(C[i*t-1][(i-j)*t],fac[j*t-1]),f[i-j]));
			for(int re i=1;i*t<=n;++i)
				Inc(ord,mul(mul(C[n][i*t],fac[n-i*t]),f[i]));
		}
		ans=(ll)ans*po(p,ord)%mod;
	}cout<<ans<<"\n";
}

inline void file(){
#ifdef zxyoi
	freopen("exercise.in","r",stdin);
#else
#ifndef ONLINE_JUDGE
	freopen("exercise.in","r",stdin);
	freopen("exercise.out","w",stdout);
#endif
#endif
}signed main(){file();Main();return 0;}