LOJ3284 「USACO 2020 US Open Platinum」Exercise

Link
对于一个置换，它的阶为它分解得到的循环的长度的\(\operatorname{lcm}\)。
考虑分别计算答案中所有\(p\le n\)的指数。
设一个置换划分后的循环长度为\(l_1,\cdots,l_m\)，那么它对\(p\)的贡献就是\(\max\limits_{i=1}^m(\operatorname{ord}_p(l_i))\)。
利用min-max和等于转大于等于将其转化为\(\sum\limits_{e=1}^{\log_pn}\sum\limits_{S\subseteq\{0,\cdots,m\}}(-1)^{|S|+1}\prod\limits_{i\in S}[\operatorname{ord}_p(l_i)\ge e]\)。
枚举\(p,e\)，记\(t=p^e\)，设\(f_i\)表示为\(t\)的倍数循环的总长度为\(it\)的方案数，转移为\(f_i=-\sum\limits_{j=1}^i{it-1\choose i-j}(i-j)!f_{i-j}\)。
这个\(-1\)就是由\((-1)^{|S|+1}\)得来的。
有\(f(t)=\sum\limits_{i=1}^{\lfloor\frac nt\rfloor}{n\choose it}(n-it)!f_i\)个置换中有至少一个循环的长度为\(t\)的倍数。
简单分析可以发现答案就是\(\prod\limits p^{\sum\limits f(p^e)}\)。

#include<cstdio>
#include<vector>
#include<cstring>
const int N=7507;
int P,phi,C[N][N],fac[N],is[N],f[N];std::vector<int>pr;
void inc(int&a,int b){a+=b-phi,a+=a>>31&phi;}
int mul(int a,int b){return 1ll*a*b%phi;}
int pow(int a,int k){int r=1;for(;k;k>>=1,a=1ll*a*a%P)if(k&1)r=1ll*a*r%P;return r;}
int main()
{
    int n,ans=1;scanf("%d%d",&n,&P),phi=P-1;
    for(int i=0;i<=n;++i) for(int j=C[i][0]=1;j<=i;++j) inc(C[i][j]=C[i-1][j],C[i-1][j-1]);
    for(int i=fac[0]=1;i<=n;++i) fac[i]=mul(i,fac[i-1]);
    for(int i=2,j;i<=n;++i) if(!is[i]) for(pr.push_back(i),j=i*2;j<=n;j+=i) is[j]=1;
    for(int p:pr)
    {
        int r=0;
        for(int t=p,e=1;t<=n;t*=p,++e)
	{
	    memset(f+1,0,n/t*4),f[0]=phi-1;
	    for(int i=1;i*t<=n;++i) for(int j=1;j<=i;++j) inc(f[i],phi-mul(mul(C[i*t-1][j*t-1],fac[j*t-1]),f[i-j]));
            for(int i=1;i*t<=n;++i) inc(r,mul(mul(C[n][i*t],fac[n-i*t]),f[i]));
        }
	ans=1ll*ans*pow(p,r)%P;
    }
    printf("%d",ans);
}

LOJ3284 「USACO 2020 US Open Platinum」Exercise

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12723261.html