题目链接

P6276 [USACO20OPEN] Exercise P

题意简述

求所有长度为 $n$ 的排列的所有置换环长度的 $\operatorname*{lcm}$ 的乘积。

$1 \le n \le 7500$。

解题思路 & 参考代码

根据 $\min,\max$ 容斥有 $\gcd,\operatorname*{lcm}$ 容斥：$\operatorname*{lcm}_{x \in S} x = \prod_{T \subseteq S}(\gcd_{x \in T} x)^{(-1)^{|T| - 1}}$。

于是原问题被转化为了对子集的 $\gcd$ 计数，注意要带上容斥系数。

考虑钦定 $\gcd$ 为 $x$ 来计算答案。

为了方便计算，考虑先预处理出 $f_i$ 表示 $i$ 个位置分成若干个置换环的方案数，考虑钦定新增的环在首位，有转移：

$$f_{i+j} \gets f_i \times \binom{i+j-1}{j-1} \times (j-1)!$$

然后进行 dp，$g_i$ 表示凑出 $ix$ 的方案数（带容斥系数）：

$$g_{j+k} \gets (-1) \times g_j \binom{(j+k)\times x-1}{k \times x-1} \times (k \times x - 1)!$$

那么钦定 $\gcd = x$ 的答案 $ans_x = \displaystyle\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor} g_i f_{n-ix}\binom{n}{ix}$。

对着 $ans$ 容斥一下即可还原出 $\gcd$ 严格为 $x$ 的答案。

最终答案即为 $\prod_{i=1}^{n} i^{ans_i}$。

时间复杂度 $O(n^2)$。

因为 $ans_i$ 是指数上的，所以前面都要要 $\bmod \ (p - 1)$，模数不是质数，所以要 $n^2$ 预处理一下组合数。

:::info[参考代码]

int n;
int f[7510],g[7510],ans[7510];
int C[7510][7510],A[7510][7510];
int fac[7510];
void solve()
{
    cin>>n>>mod;
    mod--;
    fac[0]=1;
    forl(i,1,7505)
        fac[i]=1ll*fac[i-1]*i%mod;
    C[0][0]=1;
    forl(i,1,7505)
    {
        A[i][0]=C[i][0]=1;
        forl(j,1,i)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod,
            A[i][j]=1ll*C[i][j]*fac[j]%mod;
    }
    f[0]=1;
    forl(i,0,7500)
        forl(j,1,7500-i)
        {
            if(i!=0)
                add(f[i+j],1ll*f[i]*A[i+j-1][j-1]%mod);
            else
                add(f[i+j],1ll*f[i]*fac[j-1]%mod);
        }
    forl(i,1,n)
    {
        ll lim=n/i;
        forl(j,0,lim+5)
            g[j]=0;
        g[0]=mod-1;
        forl(j,0,lim)
            forl(k,1,lim-j)
            {
                if(j!=0)
                    add(g[j+k],mod-1ll*g[j]*A[(j+k)*i-1][k*i-1]%mod);
                else
                    add(g[j+k],mod-1ll*g[j]*fac[k*i-1]%mod);
            }
        forl(j,1,lim)
            add(ans[i],1ll*g[j]*f[n-i*j]%mod*C[n][i*j]%mod);
    }
    forr(i,n,1)
        forll(j,i*2,n,i)
            add(ans[i],mod-ans[j]);
    mod++;
    long long S=1;
    forl(i,1,n)
        S=S*pw(i,ans[i],mod)%mod;
    cout<<S<<endl;
}

:::