题解 [ABC321G] Electric Circuit

· · 题解

\text{Solution}

给你 $n$ 个点和两个长度为 $m$ 的序列 $r,b$，表示点 $r_i$ 向点 $b_i$ 连一条边。你可以将 $b$ 序列重排，求所有连边方案的连通块个数和。最后除 $m!$ 即为期望。 我们肯定不能对每个序列求答案，所以考虑计算每个连通块对答案的贡献。$n\leq 17$ 容易想到状压，枚举子集。 设 $cr_i=\sum\limits_j[r_j=i],cb_i=\sum\limits_j[b_j=i],R(S)=\sum\limits_{i\in S} cr_i,B(S)=\sum\limits_{i\in S}cb_i$。 设 $f(S)$ 表示点集 $S$ 为一个独立连通块的方案数。你发现这说明点集 $S$ 里的点只能在内部连边，也就是 $R(S)=B(S)$。在集合内连边的总方案数为 $R(S)!$，要减去 $S$ 是若干独立连通块的情况，枚举独立的连通块 $T$，**经典钦定 $lowbit(S)\in T$ 去重一种方案被多个子集枚举到。** $$ f(S)=R(S)!-\sum\limits_{T,lowbit(S)\in T} f(T)\times R(S/T)! $$ 一开始我以为这样就做完了，但是把若干连通块拼起来，方案数应该要乘起来。 我觉得比较自然的应该是先想到设 $g(S,i)$ 表示将 $S$ 拆成 $i$ 个连通块的方案数复杂度为 $O(n3^n)$。 发现不能枚举个数，转而直接求个数和，设 $g(S)$ 表示 $S$ 拆成若干连通块的不同方案的块数之和。枚举 $T$ 作为新加入一个独立连通块。 $$ g(S)=\sum\limits_{T,lowbit(S)\in T}f(T)\times R(S)!+g(S/T)\times f(T) $$ $g(S)$ 即为所求，复杂度 $O(3^n)$。 ### $\text{Code} 
#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define cout cerr
#define debug cout<<"debug"<<endl;
using namespace std;
const int N=18;
const int M=1e5+5;
const int mod=998244353;
int n,m,r[M],b[M],lim;
int cr[N],cb[N],R[1<<N],B[1<<N];
ll f[1<<N],g[1<<N],fac[M];
inline int read() {
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=1; ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return f?-x:x;
}
inline void inc(ll &x,int y) {x+=y-mod;x+=(x>>63)&mod;}
inline void init() {
    fac[0]=1;
    for(int i=1;i<=m;i++) fac[i]=1LL*fac[i-1]*i%mod;
}
inline ll qpow(ll x,int y) {
    ll ret=1;
    while(y) {
        if(y&1) ret=ret*x%mod;
        x=x*x%mod,y>>=1;
    }
    return ret;
}
inline int lowbit(int x) {return x&(-x);}
int main()
{
    n=read(),m=read();
    init();
    for(int i=1;i<=m;i++) r[i]=read(),cr[r[i]]++;
    for(int i=1;i<=m;i++) b[i]=read(),cb[b[i]]++;
    lim=1<<n;
    for(int i=1;i<lim;i++) {
        for(int j=1;j<=n;j++) {
            if(i>>(j-1)&1) R[i]+=cr[j],B[i]+=cb[j];
        }
    }
    for(int s=1;s<lim;s++) {
        if(R[s]!=B[s]) continue;
        f[s]=fac[R[s]];
        for(int t=s&(s-1);t;t=s&(t-1)) {
            if(lowbit(s)&t) {
                inc(f[s],mod-f[t]*fac[R[s^t]]%mod);
            }
        }
    }
    for(int s=1;s<lim;s++) {
        g[s]=f[s];
        for(int t=s&(s-1);t;t=s&(t-1)) {
            if(lowbit(s)&t) {
                inc(g[s],(f[t]*fac[R[s^t]]%mod+f[t]*g[s^t]%mod)%mod);
            }
        }
    }
    printf("%lld",g[lim-1]*qpow(fac[m],mod-2)%mod);
    return 0;
}