题解 CF715E 【Complete the Permutations】

· · 题解

发现自己对于输入大于 O(1) 的数数题不那么在行，于是来做做这个题。

题意 : 定义两个排列的距离为 : 让两个排列变得相同，在第一个上所需交换的次数。

现在给出两个长度为 n 的排列，某些位置为 0 表示未确定，现在求两个排列距离为 0...n-1 的方案数。

对 99824435 取模。

先考虑两个已经确定的排列之间的距离。

结论 : 视作置换， (n-\text{环的个数}) 即为距离。

构造 : 只要把每个环适当旋转，就能得到正确的排列。而旋转一个大小为 m 的环只需要 m-1 次交换(对单个环达到下界)，总交换次数就是 (n-\text{环的个数}) 。

下界 : 可以证明，跨越两个环的交换是不优的，因为这打破了环的封闭性。

在一个不确定的置换中，我们会产生 4 类边（链）:

对于第一种，我们可以简单地把标号传递(可以使用并查集)，然后忽略这些边。如果已经形成环就记下。

此外，如果一组 (0\rightarrow b,a\rightarrow 0) 中 a=b ，则合成链 0\rightarrow 0 。

记处理后 ②③④ 三种链的个数分别为 n_2,n_3,m 。

我们以三步将不完整的置换填写为完整的置换 ：

此外，还要考虑成环的总个数，若成 c 个环，则加权 x^c。最终得到的幂级数即为答案。

观察发现， a_1\rightarrow 0 接上 a_2\rightarrow 0 还是得到 a_1\rightarrow 0。

而 0\rightarrow 0 接上 a\rightarrow 0 还是得到 0\rightarrow 0。

所以，只要 0\rightarrow 0 不成环（在第三步之前）， ④ 类边的个数是不变的。

而 ②③ 类边之间不会转化，这就说明三步之间是独立的。分别考虑三步的幂级数。

F_1[k]=\sum\limits_{i=k}^{n_2}\dbinom{n_2}{i}\begin{bmatrix}i\\k\end{bmatrix}(n_2+m-i-1)^{\underline{n_2-i}}

意思是，先选出 i 条链拼成 k 个环，然后把剩下 ② 类链转化为 ④ 类链。

这转化是有讲究的，我们不能再形成环，又要不留 ② 类边，只能串成若干条以 0\rightarrow 0 开头的链。

对于第一条待处理的 ② 类边，有 n_2+m-i-1 种连法，可以连到其他 ② 类边，或者 ④ 类边。

连完之后就会消失，所以下一条边少了一种方案，呈现出来就是下降幂。

考虑 ③ 类边内部获得 k 个环的方案数。和上面差不多。记为 F_2。

最后考虑 ④ 类边内部获得 k 个环的方案数。

F3[k]=\begin{bmatrix}m\\k\end{bmatrix}m!

额外的 m! 是因为我们可以在原排列上以任意顺序填写这些边。

把三个数组卷积即可。

此题的 n 较小。允许我们 O(n^2) 递推第一类斯特林数以及暴力卷积。

#include<algorithm>
#include<cstdio>
#define mod 998244353
#define ll long long
#define MaxN 255
using namespace std;
inline int read(){
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
ll powM(ll a,ll t=mod-2){
  ll ans=1;
  while(t){
    if(t&1)ans=ans*a%mod;
    a=a*a%mod;t>>=1;
  }return ans;
}
ll fac[MaxN],ifac[MaxN],s[MaxN][MaxN];
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void Init(int lim)
{
  fac[0]=1;
  for (int i=1;i<=lim;i++)
    fac[i]=fac[i-1]*i%mod;
  ifac[lim]=powM(fac[lim]);
  for (int i=lim;i;i--)
    ifac[i-1]=ifac[i]*i%mod;
  s[0][0]=1;
  for (int i=1;i<=lim;i++)
    for (int j=1;j<=i;j++)
      s[i][j]=(s[i-1][j-1]+s[i-1][j]*(i-1))%mod;
}
void get1(ll *F,int n,int m){
  if (!m){
    for (int k=0;k<=n;k++)F[k]=s[n][k];  
    return ;
  }
  for (int k=0;k<=n;k++)
    for (int i=k;i<=n;i++)
      F[k]=(F[k]+C(n,i)*s[i][k]%mod*fac[n+m-i-1]%mod*ifac[m-1])%mod;
}
int n,p1[MaxN],p2[MaxN],tp[MaxN],f[MaxN];
int findf(int u)
{return f[u]==u ? u : f[u]=findf(f[u]);}
void merge(int u,int v)
{f[findf(u)]=findf(v);}
ll F[MaxN],G[MaxN],H[MaxN];
bool v1[MaxN],v2[MaxN];
int main()
{
  Init(n=read());
  for (int i=1;i<=n;i++)f[i]=tp[p1[i]=read()]=i;
  for (int i=1;i<=n;i++)p2[i]=read();
  int cnt=0;
  for (int i=1;i<=n;i++)
    if (p1[i]&&p2[i]&&!v1[p1[i]]){
      int p=i;v1[p1[i]]=1;
      while(1){
        if (p2[p]&&tp[p2[p]])p=tp[p2[p]];
        else break;
        v1[p1[p]]=1;merge(p1[p],p1[i]);
        if (p==i){cnt++;break;}
      }
    }
  for (int i=1;i<=n;i++){
    p1[i]=findf(p1[i]);
    p2[i]=findf(p2[i]);
  }
  int n2=0,n3=0,m=0;
  for (int i=1;i<=n;i++)v1[i]=0;
  for (int i=1;i<=n;i++){
    if (!p1[i])v2[p2[i]]=1;
    if (!p2[i])v1[p1[i]]=1;
  }for (int i=1;i<=n;i++)if (v1[i]&&v2[i])m++;
  for (int i=1;i<=n;i++)
    if (p1[i]&&!p2[i]&&!v2[p1[i]])n2++;
    else if (!p1[i]&&p2[i]&&!v1[p2[i]])n3++;
    else if (!p1[i]&&!p2[i])m++;
  get1(F,n2,m);get1(G,n3,m);
  for (int i=0;i<=n2;i++)
    for (int j=0;j<=n3;j++)
      H[i+j]=(H[i+j]+F[i]*G[j])%mod;
  for (int i=0;i<=n;i++)F[i]=0;
  for (int i=0;i<=m;i++){
    ll sav=s[m][i]*fac[m]%mod;
    for (int j=0;j<=n2+n3;j++)
      F[i+j]=(F[i+j]+sav*H[j])%mod;
  }for (int i=0;i<n;i++)
    printf("%lld ",n-i-cnt>=0 ? F[n-i-cnt] : 0);puts("");
  return 0;
}