[ABC321G] Electric Circuit 状压DP

用到了好多技巧的状压DP

我们先统计总数然后除以m的阶乘就可以了

设f[i]表示状态为i的集合造成的贡献数（也就是状态为i的集合 不与集合外的点联通 且 这个集合联通块数是1 的情况数）

不与集合外的点联通的话只用考虑结合i之间连边，集合外那些点之间两边就可以啦

这个集合联通块数是1 就比较难处理了，有个技巧就是枚举包含1号的子集的f造成的贡献即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans;
const int mod=998244353,N=100010;
int jc[N],inv[N],cnt1[N],cnt2[N],tong1[1<<18],tong2[1<<18],f[1<<18];
int lowbit(int x){return x&(-x);}
int ksm(int a,int b,int mod)
{
	int res=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)res=res*a%mod;
	return res;
}
void YYCH()
{
	jc[0]=jc[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=m;++i)jc[i]=jc[i-1]*i%mod;
	inv[m]=ksm(jc[m],mod-2,mod);
	for(int i=m-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int m)
{
	if(m>n)return 0;
	return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main()
{
	cin>>n>>m;
	YYCH();
	for(int i=1,x;i<=m;++i)scanf("%lld",&x),++cnt1[x];
	for(int i=1,x;i<=m;++i)scanf("%lld",&x),++cnt2[x];
	for(int i=0;i<=(1<<n)-1;++i)
		for(int j=1;j<=n;++j)
			if(!(i&(1<<(j-1))))
			{
				tong1[i|(1<<(j-1))]=tong1[i]+cnt1[j];
				tong2[i|(1<<(j-1))]=tong2[i]+cnt2[j];
			}
	for(int i=1;i<=(1<<n)-1;++i)
	{
		if(tong1[i]==tong2[i])
		{
			f[i]=jc[tong1[i]]*jc[m-tong1[i]]%mod;
			for(int j=(i-1)&i;j;j=(j-1)&i)
			if(lowbit(i)==lowbit(j))(f[i]-=f[j]*inv[m-tong1[j]]%mod*jc[tong1[i]-tong1[j]]%mod*jc[m-tong1[i]]%mod)%=mod;
			//cout<<"-> "<<i<<" "<<f[i]<<endl;
			(ans+=f[i])%=mod;
		}
		else f[i]=0;	
	}
	((ans%=mod)+=mod)%=mod;
	cout<<ans*inv[m]%mod;
	return 0;
}