CF 715 E. Complete the Permutations

题目大意：给定两个排列$p,q$的一部分。定义两个排列$p,q$的距离为使用最少的交换次数使得$p_i=q_i$。对于所有$0\leq k\leq n-1$的所有补全方案中距离为$k$的方案数。

$\\$

将排列看成置换的话，两个完整的排列的距离为$n-m$，其中$m$为循环节个数。

现在考虑将所有存在的不完整的循环节找出来。先连边：对于每个$i$，连$a_i\to b_i$，然后若$a_i=b_j\neq 0,$则连$b_j\to a_i$。显然对于每个$i$，$a_i,b_i$只有四种情况：

$0\to x$

$x\to 0$

$0\to 0$

$x\to y$

如果出现了第$4$种边，那么我们这两个点缩成一个无实际意义的点。对于$a_i=b_j\neq 0$的情况，我们也进行同样的处理。这样就只剩上面的$3$种链了。然后再将这些链组成环。

首先有个性质，如果$x$存在，那么它只会存在于$1$或$2$中的一种链，所以对于$1$类链，其中的$x$只会向外连向一个$0$；对第二类链同理。所以如果一个环中同时存在在$1,2$类链，那么必定存在$3$类链在中间连接。

还发现，一个环可以是纯粹由$1$类或者$2$类链组成。

于是我们考虑对$1,2$类链分别处理。

以$1$类为例。设这$3$种链的数量分别为$a,b,c$。设$f_i$为组成了至少$i$个纯种$1$类环的方案数，则：

\[ f_i=\sum_{j=i}^a\binom{a}{j}\begin{bmatrix}j\\i\end{bmatrix}(a-j+c)^{\underline{a-j}} \]

首先$\binom{a}{j}$选出$j$条链，然后第一类斯特林数$\begin{bmatrix}j\\i\end{bmatrix}$将其组成$i$个环排列。最后的$(a-j+c)^{\underline{a-j}}$表示剩下的$a-j$个$1$类链还要连出去一条边。之前说了，$1$类链的$x$只能连向$0$，所以可以选择的对象有为不在环上的$1$类链和$3$类链（$a-j+c$个），又因为每个链最多只有一个入边，所以是$(a-j+c)^{\underline{a-j}}$。但是有可能在这个过程中产生新的环，于是容斥一下就好了。

设$g$为$2$类链的答案。我们将$q=f*g$。$q_i$就是纯种$1,2$类链一共有$i$个的方案数。其他的没有在环上的$1,2$类链，它们与$3$类链组合在了一起。有一下几种“原件":

$(0\to x)_n\to 0\to 0\to(x\to0)_m$

$(0\to x)_n\to 0\to 0$

$0\to 0\to (x\to 0)_m$

$0\to 0$

我们发现每种原件中有且仅有一个$0\to 0$，所以这些原件组成$i$个环的方案数就是$\begin{bmatrix}c\\i \end{bmatrix}$。所以，设$s_i=\begin{bmatrix}c\\i \end{bmatrix}$。则还要将$q$卷上$s$。

最终，有$i$个环的排列个数就是$(q*s)_i\times c!$。

对于一个环，我们可以写成$a_{p_1}\to b_{p_1}\to a_{p_2}\to b_{p_2}...\to a_{p_n}\to b_{p_{n}}\to a_{p_1}$（$a_i$为上方的排列，$b_i$为下方的排列）。对于每个$b_{p_i}=a_{p_{i+1}}=0$的位置，我们要给$b_{p_i}$一个标号，当$b_{p_i}$确定了，$a_{p_{i+1}}$的值也就确定了（但不一定等于$b_{p_i}$）。这样的$b_{p_i}$一定有$c$个，所以乘上$c!$。

下面解释为什么$a_{p_{i+1}}$不一定等于$b_{p_i}$。之前对于所有的$x\to y$，我们直接忽略了这个边（假设这个边是$a_j\to b_j$），假设现在我令$b_{p_i}=x$，那么我们应该讲$a_j\to b_j$插入$b_{p_i}\to a_{p_{i+1}}$中，即：$b_{p_i}\to a_j \to b_j \to a_{p_{i+1}}$，显然$a_{p_{i+1}}=b_j$了。

代码：

#include
    
     #define ll long long#define N 2005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}const ll mod=998244353;ll ksm(ll t,ll x) {    ll ans=1;    for(;x;x>>=1,t=t*t%mod)        if(x&1) ans=ans*t%mod;    return ans;}int n;int a[N],b[N];ll S[N][N],C[N][N];ll fac[N],ifac[N];int cnt[3];int opp[N],exi[N],exb[N];int tag[N];int cir;ll f[N],g[N];void dfs(int v,int f) {    tag[v]=1;    if(!b[v]) {        if(!f) {            cnt[2]++;        } else cnt[1]++;        return ;    }    if(exi[b[v]]) {        if(tag[exi[b[v]]]) cir++;        else dfs(exi[b[v]],f);    } else if(!f) cnt[0]++;}ll h[N];ll ans[N];int main() {    n=Get();    fac[0]=1;    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;    ifac[n]=ksm(fac[n],mod-2);    for(int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;    for(int i=0;i<=n;i++)        for(int j=0;j<=i;j++)            C[i][j]=(!j||i==j)?1:(C[i-1][j-1]+C[i-1][j])%mod;    S[0][0]=1;    for(int i=1;i<=n;i++)        for(int j=1;j<=i;j++)            S[i][j]=(S[i-1][j-1]+S[i-1][j]*(i-1))%mod;    for(int i=1;i<=n;i++) a[i]=Get();    for(int i=1;i<=n;i++) b[i]=Get();    for(int i=1;i<=n;i++) if(a[i]) exi[a[i]]=i;    for(int i=1;i<=n;i++) if(b[i]) exb[b[i]]=i;    for(int i=1;i<=n;i++) {        if(a[i]&&exb[a[i]]) continue ;        dfs(i,a[i]);    }    for(int i=1;i<=n;i++) if(!tag[i]) dfs(i,a[i]);        for(int i=0;i<=cnt[0];i++)        for(int j=i;j<=cnt[0];j++)            (f[i]+=C[cnt[0]][j]*S[j][i]%mod*fac[cnt[0]-j+cnt[2]]%mod*ifac[cnt[2]])%=mod;    for(int i=cnt[0];i>=0;i--)        for(int j=i+1;j<=cnt[0];j++)            f[i]=(f[i]-C[j][i]*f[j]%mod+mod)%mod;        for(int i=0;i<=cnt[1];i++)        for(int j=i;j<=cnt[1];j++)            (g[i]+=C[cnt[1]][j]*S[j][i]%mod*fac[cnt[1]-j+cnt[2]]%mod*ifac[cnt[2]])%=mod;                for(int i=cnt[1];i>=0;i--)        for(int j=i+1;j<=cnt[1];j++)            g[i]=(g[i]-C[j][i]*g[j]%mod+mod)%mod;    for(int i=0;i<=n;i++)        for(int j=0;j<=i;j++)            (h[i]+=f[j]*g[i-j])%=mod;    for(int i=0;i<=n;i++)        for(int j=0;j<=i;j++)            (ans[i]+=h[j]*S[cnt[2]][i-j]%mod*fac[cnt[2]])%=mod;    for(int i=n;i>=1;i--)         if(i>=cir) ans[i]=ans[i-cir];        else ans[i]=0;    for(int i=n;i>=1;i--) cout<
     
      <<" ";    return 0;}

转载于:https://www.cnblogs.com/hchhch233/p/10843395.html

你可能感兴趣的文章