AtCoder ABC #321 (サントリープログラミングコンテスト2023) : G - Electric Circuit

これは何度か見た問題。
https://atcoder.jp/contests/abc321/tasks/abc321_g

問題

N点の間に計M本の辺を張る。
M要素の数列A,Bがあり、1～Mの順列Pに対し点A[i]と点B[P[i]]の間に無向辺を張ることを考える。

Pの取り方はM!通りのうち等確率で1つ選ぶとき、出来上がるグラフの連結成分数を求めよ。

解法

以下を考える。
F(mask) := ビットマスクmaskで示す頂点集合と、他の頂点が非連結であるような、頂点集合内の辺の組み方
G(mask) := ビットマスクmaskで示す頂点集合と、他の頂点が非連結であり、かつmaskが単一の連結成分であるような、頂点集合内の辺の組み方

maskが示す頂点を端点とする辺がk本ある場合、G(mask)*(M-k)!の総和が解となる。
F(mask) = k! なので、ここから単一の連結成分でないケースを考える。
maskのうち1頂点vを定める。
mask1 ∪ mask2 = mask かつmask1がvを含むケースを総当たりする。
G(mask)はF(mask)からG(mask1)*F(mask2)を引いたものとなる。

int N,M;
int R[101010],B[101010];
int RC[17],BC[17];
ll F[1<<17]; //内部で完結
ll G[1<<17]; //
const ll mo=998244353;

const int NUM_=2000003;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>R[i];
		R[i]--;
		RC[R[i]]++;
	}
	FOR(i,M) {
		cin>>B[i];
		B[i]--;
		BC[B[i]]++;
	}
	ll ret=0;
	int mask;
	FOR(mask,1<<N) if(mask) {
		int a=0,b=0;
		FOR(i,N) if(mask&(1<<i)) {
			a+=RC[i];
			b+=BC[i];
		}
		if(a==b) {
			G[mask]=F[mask]=fact[a]%mo;
			
			int sm=mask;
			FOR(i,N) if(sm&(1<<i)) {
				sm^=1<<i;
				break;
			}
			for(int sm2=sm-1;sm2>=0;sm2--) {
				sm2&=sm;
				(G[mask]-=G[(1<<i)^sm2]*F[sm^sm2])%=mo;
			}
			G[mask]=(G[mask]%mo+mo)%mo;
			ret+=G[mask]*fact[M-a]%mo;
		}
	}
	ret=ret%mo*factr[M]%mo;
	cout<<ret<<endl;
	
}

まとめ

O(3^N+N*2^N)でN上限17はちょっと心配だったけど、どうにかなったね。