又是一道A不掉的题，怪就怪洛谷的题解实在是太短（cha）了。
尽管如此，这个题解还是要膜的。
（From https://www.luogu.org/wiki/show?name=题解+P3673 ）
求g[i][j]需要矩阵，然而我不会，所以这题只能扔掉了。
然后考虑f[i][j]：rep(i,1,n0)rep(j,1,n1)for(i1=0;i1<=i;i1+=2)rep(j1,0,j)if(i1||j1)f[i][j]+=C(i1+j1,i1)*C(i+j-i1-j1,i-i1)*g[i1+j1][i+j-i1-j1];
将计算的答案设为h[黑边数][白边数]，可用背包解决，即rep(i,1,n0)rep(j,1,n1)per(i1,n0,i)per(j1,n1,j)h[i1][j1]+=h[i1-i][j1-j]*f[i][j];
下面的代码还没调过，是会爆零的。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; #define rep(i,j,k) for(i=j;i<=k;++i) #define per(i,j,k) for(i=j;i>=k;--i) #define ll long long #define db double #define mkp(x,y) make_pair(x,y) #define pll pair<ll,ll> #define X first #define Y second const ll N=51,MOD=998244353; ll n,n1,n0,g[N][N],C[N][N],f[N][N],h[N][N];char s[N]; ll add(ll x,ll y){ ll z=x+y; if(z>MOD)z-=MOD; return z; } ll mul(ll x,ll y){ return x*y%MOD; } int main(){ ll i,j,i1,j1; scanf("%s",s);n=strlen(s); rep(i,1,n)n1+=s[i]=='1';n0=n-n1; g[1][0]=1;rep(j,1,n)g[1][j]=mul(g[1][j-1],2*j-1); rep(j,1,n)g[1][j]=mul(g[1][j],j+1); rep(i,2,n){ g[i][0]=mul(g[i-1][0],i);rep(j,1,n) g[i][j]=add(mul(g[i][j-1],i+j+j-2),mul(g[i-1][j],i-1)); } rep(i,0,n)C[i][0]=1; rep(i,1,n)rep(j,1,n)C[i][j]=add(C[i-1][j-1],C[i-1][j]); rep(i,0,n0)rep(j,0,n1)for(i1=0;i1<=i;i1+=2)rep(j1,0,j)if(i1||j1) f[i][j]=add(f[i][j],mul(mul(C[i1+j1][i1],C[i+j-i1-j1][i-i1]),g[i1+j1][i+j-i1-j1])); rep(i,1,n0)rep(j,1,n1)per(i1,n0,1)per(j1,n1,j) h[i1][j1]=add(h[i1][1],mul(h[i1-i][j1-j],f[i][j])); printf("%lld\n",h[n0][n1]); return 0; }
