题解 AT2704【[AGC019E] Shuffle and Swap】
whiteqwq
2022-01-05 16:51:12
[AT2704 [AGC019E] Shuffle and Swap](https://www.luogu.com.cn/problem/AT2704) 解题报告：
[更好的阅读体验](https://www.cnblogs.com/xiaoziyao/p/15767284.html)
## 题意
给定两个 01 串 $A,B$，令 $a,b$ 分别代表 $A,B$ 的值为 $1$ 位置序列，随机打乱 $a,b$，求按照 $1,2,\cdots,k$ 的顺序交换 $a_i,b_i$ 使得 $A=B$ 的概率。
$1\leqslant n\leqslant 10000$。
## 分析
为啥 $10^4$ 也能平方啊/yun。
考虑有用的下标只有三种情况，01/11/10，我们发现要相等就必须要将一个 $0$ 从 $01$ 传递出去，经过若干个 $11$，然后到达一个 $10$。
抽象成图论模型，有三种点（与 01/11/10 一一对应），最后的图形态一定是很多个以一类点开始，三类点结束，中间都是二类点的链。
然后考虑按照操作的顺序从前到后 dp，每次要么新建一条链，要么在一条链的尾部插入一个二类点。（只能在尾部插入，因为必须把 $0$ “传递”过去）
令 $f_{i,j}$ 表示一共新建了 $i$ 条链（也就是使用了 $i$ 个一、三类点），使用了 $j$ 个二类点的方案数，那么可以列出转移方程：
$$f_{i,j}=f_{i-1,j}\cdot i^2+f_{i,j-1}\cdot ij$$
这个转移方程的意义就是①新建一条链需要选择任意一个一类点、任意一个三类点；②在一条链的尾部插入一个二类点需要选择任意一条链、任意一个二类点。。
最后的答案只需要枚举剩余的二类点的数量：（令 $p$ 为一类点的数量，$q$ 为二类点的数量）
$$\sum_{k=0}^q {q\choose k}{p+q\choose k}\cdot(i!)^2\cdot f_{p,q-i}$$
那个 $(i!)^2$ 是因为剩余的二类点在两个序列中的位置都可以任意排列。
直接 dp 即可，复杂度 $O(n^2)$。
## 代码
```cpp
#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn=10005,mod=998244353;
int n,p,q,ans;
int f[maxn][maxn],fac[maxn],nfac[maxn],inv[maxn];
string a,b;
int main(){
cin>>a>>b,n=a.size();
for(int i=0;i<n;i++)
p+=(a[i]=='1'&&b[i]=='0'),q+=(a[i]=='1'&&b[i]=='1');
fac[0]=nfac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=1ll*fac[i-1]*i%mod,inv[i]=i==1? 1:(mod-1ll*(mod/i)*inv[mod%i]%mod),nfac[i]=1ll*nfac[i-1]*inv[i]%mod;
for(int i=0;i<=p;i++)
f[i][0]=1ll*fac[i]*fac[i]%mod;
for(int i=1;i<=p;i++)
for(int j=1;j<=q;j++)
f[i][j]=1ll*(1ll*f[i-1][j]*i+1ll*f[i][j-1]*j)%mod*i%mod;
for(int i=0;i<=q;i++)
ans=(ans+1ll*fac[q]*fac[p+q]%mod*nfac[q-i]%mod*nfac[p+q-i]%mod*f[p][q-i])%mod;
printf("%d\n",ans);
return 0;
}
```