【DP】AGC019E Shuffle and Swap

分析：

可以尝试构造每一个合法数列。
显然，如果某个位置，$A_i=1$且$B_i=1$，那么这个A中的1被拿走后，必须有一个1填回来。此类点定义为公共点。

如果某个位置，$A_i=1且B_i=0$，那么这个A中的1被拿走后，不能有其他1填进来。此类点定义为非公共点。对应的，称$A_i=0且B_i=1$的为反非公共点，

进一步分析，发现：如果是一个仅由公共点组成的循环，其顺序可以任意。这很麻烦，所以我们可以选择最后来处理这部分。

所以，定义$DP[i][j]$表示用掉i个公共点，j个非公共点，凑出j条链的方案数。（这里的链是指从一个非公共点出发，到达一个反非公共点，中间仅由公共点组成的链。

DP转移就很显然了：
$DP[i][j]=DP[i?1][j]?i?j+DP[i][j?1]?j?j$
这里还是解释一下：对于前半部分，可以视为：放入一个公共点，此公共点编号任意，所以可以和前面任意一个公共点交换，因此乘以i，并且，它可以插入任意一个链后，因此乘以j。
对于后半部分，可以视为：放入一个非公共点，次非公共带你编号任意，所以可以和前面任意一个非公共点交换，因此乘以j，并且，它可以选择任意一个反非公共点放入，因此乘以j。

虽然n有10000，但其复杂度上限为${\frac{n}{2}}^2=5000^2$，不会超时。
内存直接开即可，大约381M左右。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 10010
#define MOD 998244353
using namespace std;
typedef long long ll;
int dp[MAXN][MAXN];
char a[MAXN],b[MAXN];
int cnta,cntb;
ll fac[MAXN],ifac[MAXN];
ll ans;
ll fsp(ll x,int y){
    ll res=1;while(y){
    if(y&1)res=res*x%MOD;x=x*x%MOD;y>>=1;}	return res;
}
void prepare(){
    fac[0]=1;for(int i=1;i<=10000;i++)fac[i]=fac[i-1]*i%MOD;ifac[10000]=fsp(fac[10000],MOD-2);for(int i=10000;i>=1;i--)ifac[i-1]=ifac[i]*i%MOD;
}
ll C(int n,int m){
    return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;	
}
int main(){
    prepare();SF("%s%s",a,b);int len=strlen(a);for(int i=0;i<len;i++){
    if(a[i]=='1'){
    if(b[i]=='1')cnta++;elsecntb++;}}dp[0][0]=1;for(int i=0;i<=cnta;i++)for(int j=1;j<=cntb;j++){
    if(i!=0)dp[i][j]=1ll*dp[i-1][j]*i%MOD*j%MOD;dp[i][j]=(dp[i][j]+1ll*dp[i][j-1]*j%MOD*j%MOD)%MOD;}//PF("{%d %d}\n",dp[0][1],dp[1][1]);for(int i=0;i<=cnta;i++){
    int les=cnta-i;//PF("{%d %lld %lld %lld}\n",dp[i][cntb],fac[les],C(cnta,les),C(cnta+cntb,les));ans=(ans+1ll*dp[i][cntb]*fac[les]%MOD*fac[les]%MOD*C(cnta,les)%MOD*C(cnta+cntb,les)%MOD)%MOD;}PF("%lld",ans);
}