AT2704 [AGC019E] Shuffle and Swap 解题报告
AT2704 [AGC019E] Shuffle and Swap 解题报告：
更好的阅读体验
题意
给定两个 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(k!)^2\cdot f_{p,q-k} \]那个 \((k!)^2\) 是因为剩余的二类点在两个序列中的位置都可以任意排列。
直接 dp 即可，复杂度 \(O(n^2)\)。
代码
#include
#include
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