题意
求所有长度为 n 的排列的所有置换环的长度的最小公倍数的乘积。
题解
记长度为 $n$ 的答案为 $S_n$
写出一个很丑的原始式子：
$$ S_n = \prod\limits_{p\in P^n}{\text{lcm}_{loop\in p}{|loop|}} $$
下文记 $\mathbb{P}$ 为所有质数构成的集合。
观察式子，欲求之。
首先，硬算算不了，因为排列数实在太多了。
于是我们要想办法拆贡献。
观察发现真正产生贡献的是置换环的长度
发现式子的feature：lcm
lcm，gcd在群论体系下有另一种理解：集合的交与并，个数的$min$与$max$ 。
对于lcm，
如果记 $L=\text{lcm}_{loop\in p}{|loop|}$
将 $L$ 分解质因数：
$$ L = p_i^{\alpha_i}(p\in \mathbb{P}) $$
那么每一项质因数的指数代表了这个置换中所有置换环长度对应质因数指数的最大值
那么也就是说，每个质因数只有指数最大的置换环对答案有贡献。
由于正好计算的是乘积，那么一个质因数 $p$ ，如果在某个置换的所有置换环长度中最多出现了 $k$ 次，就对答案有 $p^k$ 的贡献（贡献全部要乘起来）.
$$ ans=\prod\limits_{p(p\in \mathbb{P})}\prod\limits_{k}p^{k\times 所有置换环长度中质因数p最多出现了k次的置换的个数} $$
这个指数看起来非常难看，最多出现 $k$ 次是个很严格的限制。
这里要用一个数论trick：
与其在 $k$ 枚举到最大值了才把 $k$ 个 $p$ 一次贡献到答案中，不如每枚举到一次不超过最大值的都给答案贡献一个 $p$。
$$ ans=\prod\limits_{p^k,p\in \mathbb{P}}{p^{存在一个置换环的长度为p^k的倍数的置换的个数}} $$
这里就像先贡献一个 $p$ ，然后所有数都去掉一个 $p$，然后重复上述操作。
对于 $n$ 阶的排列，
$$ S_n = \prod\limits_{p^k,p\in \mathbb{P}}{p^{存在一个置换环的长度为p^k的倍数的n阶置换的个数}} $$
于是枚举 $p^k$，计算 存在一个置换环的长度为 $p^k$ 的倍数的 $n$ 阶置换的个数
记 $x = p^k$，下列都是对于枚举的 $p^k$ 的计算。
记
$$ cnt_n = 存在一个置换环的长度为 p^k 的倍数的 n 阶置换的个数 $$
我们还是觉得“存在”的这种东西太难了，于是正难则反，由于n 阶置换的总个数是 $n!$ ，考虑求:
$$ f_n = n! - cnt_n = 不存在一个置换环的长度为 p^k 的倍数的 n 阶置换的个数 $$
这个还是太难求了。很难转移。
于是我们再换个角度考虑：“存在”不好转移，那“对于任意”呢？
记
$$ g_n = 所有置换环的长度都为 p^k 的倍数的 n 阶置换的个数 $$
我们能发现一个关系：
存在一个置换环的长度为 $p^k$ 的倍数的 $n$ 阶置换 （$cnt_n$）
可以由低阶的
不存在一个置换环的长度为 $p^k$ 的倍数的 $m$ 阶置换 （$f_m$）
和
所有置换环的长度都为 $p^k$ 的倍数的 $n-m$ 阶置换 （$g_{n-m}$）
拼出来。
而且能做到不重不漏。
于是我们现在来求 ${g_n}$。
由于置换环全是 $p^k$ 的倍数，所以$g_n$可以由前面的项转移过来。
很快我们想到了向前面的项中加入一个置换环的思路。
$n$ 个位置中，挑 $i(x|i)$ 个位置给新的置换环，剩下的由前面的 $g
$ 来转移，再乘上新的置换环有 $(i-1)!$ 种的系数。
$$ g_n = \sum\limits_{x\le i\le n,x|i}{\binom{n}{i}(i-1)!g_{n-i}} $$
用脚指头想想都知道算重了。
OI中针对重复贡献常用的trick：钦定
钦定最后一个元素一定在新加的置换环中，
这样不会存在最后一个元素被前面的 $g$ 中的置换环顶替的情况，总之做到了补充不漏。
正确的式子：
$$ g_n = \sum\limits_{x\le i\le n,x|i}{\binom{n-1}{i-1}(i-1)!\times g_{n-i}} $$
算出 $g$ 后，容易写出下来的式子：
$$ cnt_n = \sum\limits_{x\le i\le n,x|i}\binom{n}{i}g_i\times f_{n−i} $$
$$ f_n = n! - cnt_n $$
于是该分析复杂度了。
枚举了 $x$ ,每一个 $x$ 的贡献中只用转移 $\left\lfloor\frac{n}{x}\right\rfloor$ 次，每次转移需要前面 $\left\lfloor\frac{n}{x}\right\rfloor$ 个值，故每个 $x$ 转移循环次数为 $(\left\lfloor\frac{n}{x}\right\rfloor)^2$
总次数为 $\sum\limits_{x}(\left\lfloor\frac{n}{x}\right\rfloor)^2 \le \sum\limits_{x}\frac{n^2}{x^2}=n^2\times\sum\limits_{x}\frac{1}{x^2}$
后者如果你有幸见过，你一定知道一个级数：
$$ \frac{\pi^2}{6} = \sum\limits_{k=1}^{\infty}\frac{1}{k^2} $$
所以它只是一个比2小的常数，即 $O(1)$
总复杂度即为 $O(n^2)$
#include<bits/stdc++.h>
#define int long long
using namespace std;
// const int mod = 998244353;
int mod;
int qp(int x,int b){
int ret = 1;
for(;b;b>>=1){
if(b&1)ret*=x,ret%=mod;
x*=x,x%=mod;
}
return ret;
}
const int N = 7505;
const int MAXN=1e4+10;
int prime[MAXN],tot=0;bool vis[MAXN];
void Euler_sieve(int n){
for(int i=2;i<=n;i++){
if(!vis[i])prime[++tot] = i;
for(int j=1;j<=tot;j++){
if(i * prime[j] > n)break;
vis[i * prime[j]] = true;
if(i % prime[j] == 0)break;
}
}
}
int c[N][N];
int fac[N];
int n,m;
int g[N],f[N];
int work(int x){
g[0] = 1;
for(int i=x;i<=n;i+=x){
g[i] = 0;
for(int j=x;j<=i;j+=x){
g[i] += (c[i-1][j-1]*fac[j-1]%(mod-1)*g[i-j]%(mod-1));
g[i] %= (mod-1);
}
}
f[0] = 1;
for(int i=1;i<=n;i++){
if((n-i)%x!=0)continue;
f[i] = fac[i];
for(int j=x;j<=i;j+=x){
f[i] = (f[i]-(c[i][j]*g[j]%(mod-1)*f[i-j]%(mod-1))+(mod-1))%(mod-1);
}
}
return (fac[n] - f[n] + (mod-1))%(mod-1);
}
void solve(){
cin>>n>>mod;
c[0][0]=1;
fac[0] = 1;
for(int i=1;i<=n;i++){
c[i][0] = 1;
fac[i] = (fac[i-1]*i)%(mod-1);
for(int j=1;j<=n;j++){
c[i][j] = (c[i-1][j-1]+c[i-1][j])%(mod-1);
}
}
Euler_sieve(10000);
int ans = 1;
for(int i=1;prime[i]<=n;i++){
for(int x=prime[i];x<=n;x*=prime[i]){
ans = (ans * (qp(prime[i],work(x)))) % mod;
}
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int aqx = 1;
//cin>>aqx;
while(aqx--)solve();
return 0;
}