BZOJ 2313 分组 题解

---

前置知识

1. 威尔逊定理；
2. 中国剩余定理；
3. 费马小定理（欧拉定理）；
4. 组合数学。

---

题意简化

给定 $n$，$m$，设 $k$ 为将 $n$ 个数划分成多个大小一样的集合的方案数，求 $m^k \pmod{10^9 - 401}$。

---

题目分析

设 $n$ 划分成的集合大小为 $p$，那么这时方案数就是：

$$\begin{aligned} & \frac{\prod_{i=1}^{\frac{n}{p}}\begin{pmatrix} ip \\ p \end{pmatrix}}{\frac{n}{p}!} \\ & = \frac{\prod_{i=1}^{\frac{n}{p}}\frac{(ip)!}{[(i-1)p]!p!}}{\frac{n}{p}!} \\ & = \frac{\prod_{i=1}^{\frac{n}{p}}\frac{(ip)!}{[(i-1)p]!}}{\frac{n}{p}!(p!)^{\frac{n}{p}}} \\ & = \frac{n!}{\frac{n}{p}!(p!)^{\frac{n}{p}}} \\ \end{aligned} $$

而因为大小要相等，我们知道 $p$ 肯定是 $n$ 的约数，所以总方案数 $k$ 就是：

$$k = \sum_{p|n}\frac{n!}{\frac{n}{p}!(p!)^{\frac{n}{p}}} $$

设 $P=10^9 - 401$ 那么最后求得的答案为：

$$m^{\sum_{p|n}\frac{n!}{\frac{n}{p}!(p!)^{\frac{n}{p}}}} \pmod P \\ $$

而我们知道根据欧拉定理，这个大指数就可以降幂，变成形如下面的式子：

$$\begin{aligned} & m^{\sum_{p|n}\frac{n!}{\frac{n}{p}!(p!)^{\frac{n}{p}}}} \pmod P \\ & = m^{\sum_{p|n}\frac{n!}{\frac{n}{p}!(p!)^{\frac{n}{p}}}\pmod {\varphi{(P)}}} \pmod P \\ \end{aligned} $$

同时我们又发现作为模数的 $10^9-401$ 是一个质数，那么欧拉定理退化成费马小定理：

$$\begin{aligned} & m^{\sum_{p|n}\frac{n!}{\frac{n}{p}!(p!)^{\frac{n}{p}}}\pmod {\varphi{(P)}}} \pmod P \\ & = m^{\sum_{p|n}\frac{n!}{\frac{n}{p}!(p!)^{\frac{n}{p}}}\pmod {P-1}} \pmod P \\ \end{aligned} $$

看着这个式子似乎还是不太好做，那我们想一下有什么与阶乘相关的数论知识：明显是威尔逊定理。但是又出现了一个问题，威尔逊定理要求模数是质数，而 $P-1$ 明显不是质数，我们需要一种方法转换它，这时候就想到了性质非常契合的中国剩余定理：我们把 $P-1$ 拆成几个质数 $p_1 \dots p_n$，然后就可以通过下面的式子算出来：

设 $X$ 是我们要求的指数，$Y$ 是 $X$ 降幂之后的值，则 $X \equiv Y \pmod{P-1}$，它们满足以下线性同组方程组：

$$\forall i \in [1,n],p_i | (P-1) \\ \begin{cases} X \equiv y_1 \pmod {p_1} \\ X \equiv y_2 \pmod {p_2} \\ \cdots \\ X \equiv y_n \pmod {p_n} \\ \end{cases} $$

那么我们对每个质数 $p_i,i \in [1,n]$ 分别把 $y_i$ 求出来，最后再放到一起用中国剩余定理合并，就可以得出 $Y$。

我们处理完，发现 $P-1 = 2 \times 13 \times 5281 \times 7283$，也就是说 $\{ p_i \} =\{2,13,5281,7283\}$。

那么我们只需要求出对于每个 $p_i$，$\frac{n!}{\frac{n}{p}!(p!)^{\frac{n}{p}}} \pmod {p_i}$ 的值是多少，容易发现这是威尔逊定理的模版。

---

CODE

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i=(a);i>=(int)(b);--i)
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=1e4+10,MOD[5]= {999999599,2,13,5281,7283};
namespace Modular_Arithmetic {
#define Toadd(a,b) ((a)=add((a),(b)))
#define Tomul(a,b) ((a)=mul((a),(b)))
#define toadd(x,a,b) ((a)=(x).add((a),(b)))
#define tomul(x,a,b) ((a)=(x).mul((a),(b)))
	struct Modular {
		int MOD;
		int fac[N];
		template<typename T1,typename T2>constexpr auto add(T1 a,T2 b) {
			return a+b>=MOD?a+b-MOD:a+b<0?a+b+MOD:a+b;
		}
		template<typename T1,typename T2>constexpr auto mul(T1 a,T2 b) {
			return (1ll*a*b%MOD+MOD)%MOD;
		}
		template<typename T,typename...Types>constexpr auto add(T a,Types... b) {
			return add(a,add(b...));
		}
		template<typename T,typename...Types>constexpr auto mul(T a,Types... b) {
			return mul(a,mul(b...));
		}
		int Pow(int a,int b) {
			int res=1;
			for(a%=MOD; b; b>>=1,Tomul(a,a))if(b&1)Tomul(res,a);
			return res;
		}
		int _Pow(int n) {
			int cnt=0;
			for(; n; n/=MOD,cnt+=n);
			return cnt;
		}
		int Inv(int x) {
			return Pow(x,MOD-2);
		}
		int Fac(int n) {
			int res=1;
			for(; n>1; Tomul(res,fac[n%MOD]),n/=MOD)if((n/MOD)&1)res=MOD-res;
			return res;
		}
		void Init() {
			fac[0]=1;
			FOR(i,1,MOD-1)fac[i]=mul(fac[i-1],i);
		}
		int Solve(int n,int m) {
			return _Pow(n)-_Pow(m)>_Pow(n/m)*m?0:mul(Fac(n),Inv(Fac(m)),Inv(Pow(Fac(n/m),m)));
		}
	} M[5];
	void Init() {
		FOR(i,0,4) {
			M[i].MOD=MOD[i];
			if(i)M[i].Init();
		}
	}
} using namespace Modular_Arithmetic;
int Cas,n,m,ans,mod;
int a[N];
vector<int> Divide(int x) {
	vector<int> vec;
	vec.clear();
	for(int i=1; i*i<=x; ++i)if(x%i==0) {
			vec.push_back(i);
			if(i*i!=x)vec.push_back(x/i);
		}
	return sort(vec.begin(),vec.end()),vec;
}
signed Cmain() {
	cin>>n>>m,RCL(a,0,a,1);
	vector<int> factors=Divide(n);
	FOR(i,1,4)for(int &x:factors)toadd(M[i],a[i],M[i].Solve(n,x));
	ans=a[4],mod=MOD[4];
	DOR(i,3,1) {
		while(ans%MOD[i]!=a[i])ans+=mod;
		mod*=MOD[i];
	}
	cout<<M[0].Pow(m,ans)<<endl;
	return 0;
}
signed main() {
	for(Init(),cin>>Cas; Cas; --Cas)Cmain();
	return 0;
}

---

后记

这是一道数论好题，难得地集齐了四大数论定理，当然还可以用扩展卢卡斯定理做（但我不会），值得拿来练手，加深印象，其中对中国剩余定理的运用也是我先前所不知道的，这道题对数论能力真的非常有帮助。

---