[数学记录]AT2704 [AGC019E] Shuffle and Swap
command_block
2021-04-29 09:05:33
**题意** ： 给出两个长度为 $n$ 的 $01$ 串 $A,B$。
两个串均恰有 $k$ 个 $1$。令 $a_{1\sim k},b_{1\sim k}$ 分别表示 $A,B$ 中所有 $1$ 出现的位置。
将 $a$ 和 $b$ 等概率随机打乱，按 $1\sim k$ 的顺序交换 $A_{a_i}$ 和$A_{b_i}$。
令 $P$ 表示操作完成后 $A$ 与 $B$ 相等的概率，求$P\times(k!)^2$ 模 $998244353$ 。
$|A|=|B|\leq 10^4$ ，时限$\texttt{2s}$。
------------
$a,b$ 分别打乱，相当于只将 $a$ 打乱，然后按照某种顺序执行交换。
将 $a_i,b_i$ 之间连边 $a_i\rightarrow b_i$。
不难发现，由于每个点至多只有一个出边，也至多只有一个入边，故整张图是由若干个环和链组成。
- 考虑在给定图之后，合法的执行顺序数。
环中的点都是 $1$ ，所以怎么交换是无所谓的。
链条必须按照从头到尾的顺序执行，方案数唯一。
记 $A_i=1,B_i=0$ 的位置（链的开头）个数为 $c$ ，$A_i=0,B_i=1$ 的位置（链的结尾）个数也为 $c$。
最终形成的图中必有 $c$ 条链。
考虑 EGF 计数，将各个子结构标号归并。
交换也可以利用归并处理，但不这么考虑。共有 $k$ 步交换，先默认交换方案数为 $k!$ ，对于一条长为 $l$ （边数）的链，将方案数除以 $l!$。（考虑为额外加权）
（这样，我们的 EGF 就是只处理标号的经典 EGF）
链的开头结尾两类点在标号分配上不是自由的，故最后再考虑他们。先考虑自由拼接的一入度一出度的点。
对于一条长度为 $i$ 的链，有 $i-1$ 个自由点，连接方案数为 $(i-1)!$ ，边数为 $i$ ，构造的生成函数为 $\dfrac{z^{i-1}}{i!}$。
对于一个大小为 $i$ 的环，有 $i$ 个自由点，连接方案数为 $(i-1)!$ ，构造的生成函数为 $\dfrac{z^i(i-1)!}{i!}=\dfrac{z^i}{i}$。
两者的 EGF 分别为 ：
$$
\begin{aligned}
F_1(z)&=\sum\limits_{i=1}\dfrac{z^{i-1}}{i!}=\dfrac{e^z-1}{z}\\
F_2(z)&=\sum\limits_{i=1}\dfrac{z^i}{i}=\ln\big(\tfrac{1}{1-x}\big)
\end{aligned}
$$
链的个数是确定的 $c$ 个，而环的个数是不定的。
自由点的个数为 $k-c$ ，则我们要计算的是
$$
\begin{aligned}
&\left[\tfrac{z^{k-c}}{(k-c)!}\right]F_1(z)^c\exp F_2(z)\\
=&\left[\tfrac{z^{k-c}}{(k-c)!}\right]\Big(\dfrac{e^z-1}{z}\Big)^c\frac{1}{1-x}
\end{aligned}
$$
然后我们要将链头链尾拼上去。 $F_1(z)^c$ 可以看做先按顺序链的起点，然后一个个往上面安中间的部分，然后将后面的部分拼上去，这一步方案数要额外乘以 $c!$。
最后乘上交换方案数中的 $k!$ ，大功告成。
那么问题转化为对 $m=0\sim k-c$ 计算 :
$$
\begin{aligned}
&[z^m]\Big(\dfrac{e^z-1}{z}\Big)^c\\
=&[z^{m+c}](e^z-1)^c\\
=&[z^{m+c}]\sum\limits_{i=0}^{c}\dbinom{c}{i}e^{iz}(-1)^{c-i}\\
=&\sum\limits_{i=0}^{c}\dbinom{c}{i}\dfrac{i^{m+c}}{(m+c)!}(-1)^{c-i}\\
\end{aligned}
$$
复杂度 $O(n^2)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
#define MaxN 10500
using namespace std;
const int mod=998244353;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
ll fac[MaxN],ifac[MaxN];
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
}
ll pw[MaxN];
ll calc(int n,int c)
{
ll ret=0;
for (int i=0;i<=c;i++)pw[i]=powM(i,c);
for (int m=0;m<=n;m++){
ll sav=0;
for (int i=0;i<=c;i++){
if ((c-i)&1)sav=(sav-ifac[i]*ifac[c-i]%mod*pw[i])%mod;
else sav=(sav+ifac[i]*ifac[c-i]%mod*pw[i])%mod;
pw[i]=pw[i]*i%mod;
}ret=(ret+fac[c]*ifac[m+c]%mod*sav)%mod;
}return (ret+mod)%mod;
}
char a[MaxN],b[MaxN];
int main()
{
scanf("%s%s",a,b);
int n=strlen(a),k=0,c=0;
for (int i=0;i<n;i++){
if (a[i]=='1')k++;
if (a[i]=='1'&&b[i]=='0')c++;
}Init(k);
printf("%lld",fac[k]*fac[c]%mod*fac[k-c]%mod*calc(k-c,c)%mod);
return 0;
}
```