[USACO20OPEN] Exercise P

有意思的计数题。

题目链接

题意

求所有长度为 \(n\) 的排列的所有环长的 \(\text{lcm}\) 的乘积。

• \(n\leq 7500\)

解法

先 min-max 容斥把 \(\text{lcm}\) 换成 \(\gcd\)。

求 \(\prod\limits_{\sigma} \prod \limits_{T\neq \emptyset} \gcd(T)^{(-1)^{|T|}}\)，其中 \(T\) 表示环的大小的（可重）集合。

莫反，得到式子 \(\prod\limits_{d=1}^n d^{\sum\limits_{p} \mu(p) \sum\limits_{\sigma} \sum\limits_{T\neq \emptyset} [\forall i,(d\times p)\mid T_i] (-1)^{|T|}}\)。

现在要对 \(d,p\) 求出所有排列的满足每个元素是 \(d\times p\) 的倍数的环长集合的带符号的和。

朴素的 dp 可以设计状态 \(f_{i,j,k,u}\) 表示考虑长度为 \(i\) 的排列中，大小为 \(j\) 且其中环长都是 \(k\) 的倍数且所有环长和为 \(u\) 的集合的数量。

这个计数是无标号的，需要每次转移钦定当前选的环在序列中最靠右的位置是当前所有环上的位置中最靠右的。

由于要容斥，\(j\) 那一维只记奇偶即可。

但是复杂度仍然是很高的，除了暴力分啥都跑不了。

考虑精简一下状态。

我们发现，只需要知道对于长度为 \(u\) 的排列，每个环是 \(k\) 的倍数，且总长度是 \(u\) 的环的集合的数量，放在长度为 \(n\) 的排列里的可以乘上组合数，并且要求剩下 \(n-u\) 个数乱排即可。

同样地，转移的时候需要钦定当前加入的环的最右端点在当前排列的最后，满足无标号。

状态数就是 \(O(\sum \frac{n}{k})=O(n\ln n)\) 的。

转移需要 \(O(\frac{n}{k})\) 的复杂度，总的复杂度是 \(O(\sum \frac{n}{k^2})=O(n^2)\) 的。

最后统计答案也容易做到 \(O(\sum \frac{n}{k^2})=O(n^2)\)。

需要注意，我们 dp 的值在指数上，所以要模 \(\text{mod}-1\)。

参考代码

#include<bits/stdc++.h>

using namespace std;
using E=long long;
E mod,mods;
const int N=7555;

E ksm(E a,E b){
  E ret=1;
  b=(b%mods+mods)%mods;
  while(b){
    if(b&1) ret=ret*a%mod;
    a=a*a%mod;
    b>>=1;
  }
  return ret;
}

int n;

vector<int> dp[N][2];
int C[N][N];
E fac[N];
bitset<N> st;
vector<int> pr,mu;

int main(){

  cin>>n>>mod; mods=mod-1;
  mu.resize(n+1);

  fac[0]=1;
  for(int i=1; i<=n; i++) fac[i]=fac[i-1]*i%mods;

  C[0][0]=1;
  for(int i=1; i<=n; i++){
    for(int j=0; j<=i; j++){
      C[i][j]=C[i-1][j];
      if(j) C[i][j]=(C[i][j]+C[i-1][j-1])%mods;
    }
  }

  mu[1]=1;
  for(int i=2; i<=n; i++){
    if(!st[i]){
      pr.emplace_back(i);
      mu[i]=-1;
    }
    for(auto p:pr){
      if(p*i>n) break;
      st[p*i]=1;
      if(i%p==0){
        mu[i*p]=0;
        break;
      }
      mu[i*p]=mu[i]*mu[p];
    }
  }

  for(int t=1; t<=n; t++){
    for(int j:{0,1}) dp[t][j].resize(n/t+10);
    dp[t][0][0]=1;
    for(int i=1; i*t<=n; i++){
      for(int k=1; k<=i; k++){
        for(int j=0; j<=1; j++){
          dp[t][j][i]=(dp[t][j][i]+dp[t][j^1][i-k]*1ll*C[i*t-1][k*t-1]%mods*fac[k*t-1])%mods;
        }
      }
    }
  }

  E ans=1;
  for(E d=1; d<=n; d++){
    E x=0;
    for(E p=1; p*d<=n; p++){
      for(int sum=1; sum*p*d<=n; sum++){
        x=(x+mu[p]*(dp[p*d][1][sum]*1ll-dp[p*d][0][sum]+mods)%mods*C[n][sum*p*d]%mods*fac[n-sum*p*d])%mods;
      }
    }
    //cerr<<x<<endl;
    ans=ans*ksm(d,x)%mod;
  }

  cout<<ans;

  return 0;
}