其实赛时可能可以做出来的，只是打了前 6 道想下班了，有点小小遗憾。
首先问题看起来很唬人，考虑转换一下。考虑已经固定 \(m\) 条边，对于一个集合 \(S\)，什么时候会不与其他点有边。容易发现，此时需要满足 \(\sum[R_i\in S]=\sum [B_j\in S]\)。记这个数为 \(c_S\)。但是这还不够，因为 \(S\) 中点连边方案数还没有计算。
这个答案显然不是 \(c_S!\)。因为 \(S\) 可能可以分成两个集合 \(s,t\) 都满足上述条件，则会重复计算。考虑如何去重。设 \(dp_s\) 为集合 \(S\) 的答案。我们钦定 \(t\) 包含 \(S\) 里最小的元素，则有 \(dp_s=c_s!-\sum_{t\in S} dp_t\times (c_s-c_t)!\)。
然后怎么办呢？
作者表示再做一遍 dp，\(O(m3^m)\) 解决。还真过了。
但是事实上 \(ans=\sum dp_s\times (m-c_s)!\)。解决。
code：
点击查看代码
int n,m,e[23],d[23],f[N],g[N],h[N],c[N];
il int Mod(int x,int y){return x+y>=mod?x+y-mod:x+y;}
il int lowbit(int x){return x&(-x);}
il int qpow(int x,int y){
int ret=1;
while(y){
if(y&1)ret=1ll*ret*x%mod;
x=1ll*x*x%mod;y>>=1;
}
return ret;
}
void Yorushika(){
scanf("%d%d",&n,&m);
f[0]=1;
rep(i,1,m){
int x;scanf("%d",&x);
e[x]++;
f[i]=1ll*f[i-1]*i%mod;
}
rep(i,1,m){
int x;scanf("%d",&x);
d[x]++;
}
const int k=1<<n;
int ans=0;
rep(i,1,k-1){
rep(j,0,n-1){
g[i]+=e[j+1]*(i>>j&1);
h[i]+=d[j+1]*(i>>j&1);
}
if(g[i]!=h[i])
continue;
c[i]=f[g[i]];
for(int j=(i-1)&i;j;j=(j-1)&i){
if(g[j]!=h[j]||lowbit(i)!=lowbit(j))
continue;
c[i]=Mod(c[i],mod-1ll*c[j]*f[g[i]-g[j]]%mod);
}
ans=Mod(ans,1ll*c[i]*f[m-g[i]]%mod);
}
printf("%lld\n",1ll*ans*qpow(f[m],mod-2)%mod);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}