AtCoder Regular Contest 115 #D

Solution1

考虑用$\text{FWT}$来理解这个式子，容易发现$\text{FWT}$之后求积的式子，满足

对于任意$(u_i,v_i)$

如果$u_i,v_i$中有一者被选择，答案为0，否则权值$\times 2$

那么显然对于一个连通块，设其大小为$c$，放在一起考虑

在$\text{FWT}$的式子里它们同时出现或者同时不出现

枚举最后$\text{FWT}$回来时的项与在这$c$个位置中出现$i$个

对于选择这个连通块的情况，贡献为$(-1)^i$

对于不选的情况，贡献为$1$

显然只有$2|i$时贡献为2，乘上组合数完成转移，连通块之间背包合并

就能得到最终计算答案的项中出现了几个1，然后与$\text{FWT}$的系数合并即可

Solution2

对于一个连通块，考虑取出一个生成树

容易发现，仅使用这个生成树上的边，就能构成任何一个包含$2k$个奇点的情况

对于多余的边，类似异或线性基，它们都是可选可不选的

于是直接统计答案即可

Sol1 和 Sol2 的式子是一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int N=5010,P=998244353;
int n,m,dp[N];
ll qpow(ll x,ll k=P-2){
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
vector <int> G[N];
int c,vis[N],C[N][N];
void dfs(int u){
	if(vis[u]) return;
	vis[u]=1,c++;
	for(int v:G[u]) dfs(v);
}

int main(){
	n=rd(),m=rd();
	rep(i,0,n) rep(j,*C[i]=1,i) C[i][j]=C[i-1][j]+C[i-1][j-1],Mod1(C[i][j]);
	rep(i,1,m) {
		int u=rd(),v=rd();
		G[u].pb(v),G[v].pb(u);
	}
	dp[0]=1;
	rep(u,1,n) if(!vis[u]) {
		c=0,dfs(u);
		drep(i,n,0) {
			int s=0;
			rep(j,0,min(i,c)) if(~j&1) {
				s=(s+2ll*dp[i-j]*C[c][j])%P;
			}
			dp[i]=s;
		}
	}
	int d=qpow(2,P-1-n+m);
	rep(i,0,n) printf("%d\n",int(1ll*dp[i]*d%P));
}