CF715E - Complete the Permutations
题目大意
对于两个排列p,q,令p→q代价为通过交换使得p变成q的最小步数
现在部分给定了p和q,求所有情况下,p→q=i,i∈[0,n−1]的排列组数目
分析
排列变换显然要放到置换环上考虑,考虑两个排列之间的变换有多种等价的方式
不妨认为连的边就是pi→qi,最终操作步数就是n−置换环的个数
对于已经确定的部分,能够确定的边可以直接连,能够确定的链可以缩成点
那么最终,图上只剩下三种待定的边
0→0,0→x,x→0,其中0→x,x→0表示一条出现了一半的边
ps: 如果有0→x→0,那么直接缩成一个0→0看待
不妨设这三种边个数分别为A,B,C,已经确定的环可以数出是D最后加入答案
由于一个A由两边确定,实际上确定一个边组之后,排列0→0的位置得到A!种方案,也可以最后加入答案
考虑什么样的边可以接成环
仅A:0→0,0→0⋯
仅B: 0→x,0→x⋯
仅C: x→0,x→0,⋯
A+B=A,0→x+0→0=0→0
C+A=A,0→0+x→0=0→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个点选出)
这就是第一类斯特林数[ij],参考
剩下的加入组合环中,考虑依次加入每个B,每个B可以接在B后面也可以接在A后面
方案数即A¯¯¯¯¯¯¯¯¯¯B−i,最终计算得到Gi表示B构成了i个单纯B环的方案数,复杂度为O(n2)
A的贡献不需要将组合环和单纯A环分开考虑,直接就是Fi=[Ai]
最后将三种点背包合并,加入前面提到的常量即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #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; 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]); }
|
进一步的优化?
Fi的计算时标准的第一类斯特林数行,用倍增法求上升幂即可
G(x)=B∑i=0A¯¯¯¯¯¯¯¯¯¯B−i(Bi)x¯i
把系数拿出来,可以直接做一个上升幂多项式转普通多项式
复杂度为O(nlog2n)
(听说可以O(nlogn)但是我没有脑子只会套板子哈哈哈哈)
以下未上传!!!如果看到说明我在搞笑!!!看到叫我
Gi=B∑j=i(Bj)A¯¯¯¯¯¯¯¯¯¯¯B−j⋅[xj]1i!(−1)ilni(1−x)
Gi=B∑j=iB!j!(B−j)!(A+B−j−1)!(A−1)!⋅[xj]1i!(−1)ilni(1−x)
Gi=(−1)iB!(A−1)!i!B∑j=i(A+B−j−1)!j!(B−j)!⋅[xj]lni(1−x)
由于对于每个i,B∑j=i(A+B−j−1)!j!(B−j)!是常量,设
φ(x)=B∑j=0x−1−j(A+B−j−1)!j!(B−j)!(为什么是是−1−j会在下面出现)
Gi=(−1)iB!(A−1)!i![x−1]φ(x)lni(1−x)
对比扩展拉格朗日反演的形式
[xn]H(G(x))=1n[x−1]H′(x)(1F(x))n,其中G(x)为F(x)的复合逆
得到H(x)=∫φ(x),F(x)=1ln(1−x)
从而得到F(x)的复合逆为1−ex−1
现在要算H(1−ex−1)=∑