CF715E - Complete the Permutations

题目大意

对于两个排列 \(p,q\) ，令 \(p\rightarrow q\) 代价为通过交换使得 \(p\) 变成 \(q\) 的最小步数

现在部分给定了 \(p\) 和 \(q\) ，求所有情况下， \(p\rightarrow q=i,i\in[0,n-1]\) 的排列组数目

分析

排列变换显然要放到置换环上考虑，考虑两个排列之间的变换有多种等价的方式

不妨认为连的边就是 \(p_i\rightarrow q_i\) ，最终操作步数就是 \(n-\) 置换环的个数

对于已经确定的部分，能够确定的边可以直接连，能够确定的链可以缩成点

那么最终，图上只剩下三种待定的边

\(0\rightarrow 0,0\rightarrow x,x\rightarrow 0\) ，其中 \(0\rightarrow x,x\rightarrow 0\) 表示一条出现了一半的边

ps: 如果有 \(0\rightarrow x\rightarrow 0\) ，那么直接缩成一个 \(0\rightarrow 0\) 看待

不妨设这三种边个数分别为 \(A,B,C\) ，已经确定的环可以数出是 \(D\) 最后加入答案

由于一个 \(A\) 由两边确定，实际上确定一个边组之后，排列 \(0\rightarrow 0\) 的位置得到 \(A!\) 种方案，也可以最后加入答案

考虑什么样的边可以接成环

仅A: \(0\rightarrow 0,0\rightarrow 0\cdots\)

仅B: \(0\rightarrow x,0\rightarrow x\cdots\)

仅C: \(x\rightarrow 0,x\rightarrow 0,\cdots\)

A+B=A, \(0\rightarrow x+0\rightarrow 0=0\rightarrow 0\)

C+A=A, \(0\rightarrow 0+x\rightarrow 0=0\rightarrow 0\)

实际上，组合环的情况

B前面要么是B要么是A，最终将A后面跟着的小弟B都缩在一起看待

C后面要么是C要么是A，最终将A前面跟着的大哥C都缩在一起看待

实际上B,C计算类似，我们能够得到一个计算思路

将每个B,C加入组合环对于组合环缩点之后的点数无影响，那么可以将A,B,C分离计算

那么考虑一个B要么在单纯的B环上要么在组合环上

枚举有 \(i\) 个 \(B\) 在单纯B环上，构成 \(j\) 个环的方案数（当然要先组合数将 \(j\) 个点选出）

这就是第一类斯特林数 \(\begin{bmatrix}i\\j\end{bmatrix}\) ，参考

剩下的加入组合环中，考虑依次加入每个B，每个B可以接在B后面也可以接在A后面

方案数即 \(A^{\overline{B-i}}\) ，最终计算得到 \(G_i\) 表示B构成了i个单纯B环的方案数，复杂度为 \(O(n^2)\)

A的贡献不需要将组合环和单纯A环分开考虑，直接就是 \(F_i=\begin{bmatrix}A\\i\end{bmatrix}\)

最后将三种点背包合并，加入前面提到的常量即可

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
enum{N=300,P=998244353};
int n;
int p[N],q[N],pre[N],nxt[N],A,B,E,D;
int F[N],G[N],H[N],V[N];
int S[N][N],T[N][N],C[N][N];
int main(){
	scanf("%d",&n);
	rep(i,1,n) pre[i]=nxt[i]=-1;
	rep(i,**S=1,n) rep(j,1,i) S[i][j]=(S[i-1][j-1]+1ll*(i-1)*S[i-1][j])%P;
	rep(i,0,n) rep(j,*T[i]=1,n) T[i][j]=1ll*T[i][j-1]*(i+j-1)%P;
	rep(i,0,n) rep(j,*C[i]=1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
	rep(i,1,n) scanf("%d",p+i);
	rep(i,1,n) {
		scanf("%d",q+i);
		if(p[i] && q[i]) nxt[p[i]]=q[i],pre[q[i]]=p[i];
		else if(p[i]) nxt[p[i]]=0;
		else if(q[i]) pre[q[i]]=0;
	}
	rep(i,1,n) if(pre[i]<=0) {
		int j=i;
		for(;nxt[j]>0;j=nxt[j]) V[j]=1;
		V[j]=1;
		if(pre[i]==nxt[j]) A+=pre[i]==-1; // ==0 || ==-1 ,but we can't count 0 in 
		else if(~pre[i]) B++;
		else E++;
	}
	rep(i,1,n) if(!V[i]) {
		for(int j=i;!V[j];j=nxt[j]) V[j]=1;
		D++;
	}
	int c=1;
	rep(i,1,A) c=1ll*c*i%P;
	rep(i,0,A) F[i]=1ll*c*S[A][i]%P;
	rep(i,0,B) rep(j,0,i) G[j]=(G[j]+1ll*S[i][j]*T[A][B-i]%P*C[B][i])%P;
	rep(i,0,E) rep(j,0,i) H[j]=(H[j]+1ll*S[i][j]*T[A][E-i]%P*C[E][i])%P;
	
	rep(i,0,n) V[i]=0;
	rep(i,0,A) rep(j,0,B) V[i+j+D]=(V[i+j+D]+1ll*F[i]*G[j])%P;
	rep(i,0,n) F[i]=0;
	rep(i,0,A+B+D) rep(j,0,E) F[n-i-j]=(F[n-i-j]+1ll*V[i]*H[j])%P;
	rep(i,0,n-1) printf("%d ",F[i]);
}

进一步的优化？

\(F_i\) 的计算时标准的第一类斯特林数行，用倍增法求上升幂即可

\(\displaystyle G(x)=\sum_{i=0}^B A^{\overline{B-i}}\binom{B}{i} x^{\overline{i}}\)

把系数拿出来，可以直接做一个上升幂多项式转普通多项式

复杂度为 \(O(n\log ^2n)\)

（听说可以 \(O(n\log n)\) 但是我没有脑子只会套板子哈哈哈哈）

以下未上传！！！如果看到说明我在搞笑！！！看到叫我

\(\displaystyle G_i=\sum_{j=i}^B \binom{B}{j}A^{\overline{B-j}}\cdot [x^j]\frac{1}{i!}(-1)^i\ln^i(1-x)\)

\(\displaystyle G_i=\sum_{j=i}^B \frac{B!}{j!(B-j)!}\frac{(A+B-j-1)!}{(A-1)!}\cdot [x^j]\frac{1}{i!}(-1)^i\ln^i(1-x)\)

\(\displaystyle G_i=\frac{(-1)^iB!}{(A-1)!i!} \sum_{j=i}^B \frac{(A+B-j-1)!}{j!(B-j)!}\cdot [x^j]\ln^i(1-x)\)

由于对于每个 \(i\) ， \(\displaystyle \sum_{j=i}^B \frac{(A+B-j-1)!}{j!(B-j)!}\) 是常量，设

\(\displaystyle \varphi(x)=\sum_{j=0}^B x^{-1-j} \frac{(A+B-j-1)!}{j!(B-j)!}\) (为什么是是 \(-1-j\) 会在下面出现)

\(\displaystyle G_i=\frac{(-1)^iB!}{(A-1)!i!} [x^{-1}] \varphi(x)\ln^i(1-x)\)

对比扩展拉格朗日反演的形式

\(\displaystyle [x^n]H(G(x))=\frac{1}{n}[x^{-1}]H'(x)(\frac{1}{F(x)})^n\) ，其中 \(G(x)\) 为 \(F(x)\) 的复合逆

得到 \(\displaystyle H(x)=\int \varphi(x),F(x)=\frac{1}{\ln(1-x)}\)

从而得到 \(F(x)\) 的复合逆为 \(\displaystyle 1-e^{x^{-1}}\)

现在要算 \(H(1-e^{x^{-1}})=\sum\)