题解 CF715E 【Complete the Permutations】
command_block
2020-05-06 23:03:26
发现自己对于输入大于 $O(1)$ 的数数题不那么在行，于是来做做这个题。
**题意** : 定义两个排列的距离为 : 让两个排列变得相同，在第一个上所需交换的次数。
现在给出两个长度为 $n$ 的排列，某些位置为 $0$ 表示未确定，现在求两个排列距离为 $0...n-1$ 的方案数。
对 $99824435$ 取模。
------------
先考虑两个已经确定的排列之间的距离。
**结论** : 视作置换， $(n-\text{环的个数})$ 即为距离。
**构造** : 只要把每个环适当旋转，就能得到正确的排列。而旋转一个大小为 $m$ 的环只需要 $m-1$ 次交换(对单个环达到下界)，总交换次数就是 $(n-\text{环的个数})$ 。
**下界** : 可以证明，跨越两个环的交换是不优的，因为这打破了环的封闭性。
在一个不确定的置换中，我们会产生 $4$ 类边（链）:
- ① $a\rightarrow b$
- ② $a\rightarrow 0$
- ③ $0\rightarrow b$
- ④ $0\rightarrow 0$
对于第一种，我们可以简单地把标号传递(可以使用并查集)，然后忽略这些边。如果已经形成环就记下。
此外，如果一组 $(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)$ 递推第一类斯特林数以及暴力卷积。
```cpp
#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;
}
```