题解

本题使用状态压缩DP + 子集卷积 + FWT求解划分方案计数问题。

算法思路：

1. 连通性判断：

   • 对于每个子集 $S$，判断其是否连通
   • 使用 DFS 从子集中的某个点开始遍历，检查是否能访问到所有点
   • 同时判断子集是否满足欧拉性质（每个点的度数为偶数）

2. 权值计算：

   • 根据参数 $p$ 计算每个连通子集的权值：
     • $p = 0$：权值为 $1$
     • $p = 1$：权值为 $\sum_{i \in S} w_i$
     • $p = 2$：权值为 $(\sum_{i \in S} w_i)^2$

3. 子集卷积DP：

   • 状态 f[k][S]：将点集 $S$ 划分成恰好 $k$ 个连通块的方案数
   • 转移：$f[k][S] = \sum_{i=0}^{k-1} f[i][T] \times g[k-i][S \setminus T]$
   • 其中 $g[k][S]$ 表示大小为 $k$ 的连通子集 $S$ 的权值

4. FWT优化：

   • 子集卷积可以通过 FWT（Fast Walsh Transform）优化
   • 将 DP 转移从 $O(3^n)$ 优化到 $O(n^2 \cdot 2^n)$
   • FWT 实现高维前缀和的快速计算

5. 逆元处理：

   • 对于每个状态，预处理其权值的逆元 $inv[S]$
   • 在 DP 转移后，乘以逆元进行归一化处理

时间复杂度：$O(n^2 \cdot 2^n)$

这是一道结合了状态压缩DP、子集卷积和高维前缀和的高难度题目。

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define i128 __int128
#define endl '\n'
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define fi first
#define se second
#define vei vector<int>
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define yes puts("yes")
#define no puts("no")
#define Yes puts("Yes")
#define No puts("No")
#define YES puts("YES")
#define NO puts("NO")
#define In(x) freopen(x".in","r",stdin)
#define Out(x) freopen(x".out","w",stdout)
#define File(x) (In(x),Out(x))
using namespace std;
const int N=22,M=300,S=1<<21,mod=998244353;
int n,m,p,V,w[N],f[N][S],g[N][S],ppc[S],c[S],inv[S];
bool vis[N];
vector <int> ve[N];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod; 
}
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}
void dfs(int u){
	vis[u]=1;
	for(auto v:ve[u]){
		if(vis[v]) continue;
		dfs(v);
	}
}
void FWT(int V,int *f,int c){
	for(int k=1;k<V;k<<=1){
		for(int i=0;i<V;i++){
			if(i&k) continue;
			if(c==1) add(f[i|k],f[i]);
			else add(f[i|k],mod-f[i]);
		}
	}
}
void solve(){
	cin>>n>>m>>p,V=1<<n;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v,u--,v--;
		ve[u].pb(v),ve[v].pb(u);
	}
	for(int u=0;u<n;u++) cin>>w[u];
	for(int i=0;i<V;i++) for(int u=0;u<n;u++) if(i&(1<<u)) ppc[i]++;
	for(int i=0;i<V;i++){
		for(int u=0;u<n;u++){
			if(i&(1<<u)) vis[u]=0,add(g[ppc[i]][i],w[u]);
			else vis[u]=1;
		}
		if(p==0) g[ppc[i]][i]=1;
		else if(p==2) g[ppc[i]][i]=1ll*g[ppc[i]][i]*g[ppc[i]][i]%mod;
		for(int u=0;u<n;u++) if(i&(1<<u)){dfs(u);break;}
		inv[i]=ksm(g[ppc[i]][i],mod-2),c[i]=0;
		for(int u=0;u<n;u++) if(!vis[u]){c[i]=1;break;}
		if(c[i]) continue;
		for(int u=0;u<n;u++){
			if(!(i&(1<<u))) continue;
			int cnt=0;
			for(auto v:ve[u]) if(i&(1<<v)) cnt++;
			if(cnt%2==1){c[i]=1;break;}
		}
		if(!c[i]) g[ppc[i]][i]=0;
	}
	f[0][0]=1;
	FWT(V,f[0],1);
	for(int k=0;k<=n;k++) FWT(V,g[k],1);
	for(int k=1;k<=n;k++){
		for(int i=0;i<k;i++) for(int x=0;x<V;x++) add(f[k][x],1ll*f[i][x]*g[k-i][x]%mod);
		FWT(V,f[k],0);
		for(int x=0;x<V;x++){
			if(ppc[x]==k) f[k][x]=1ll*f[k][x]*inv[x]%mod;
			else f[k][x]=0;
		}
		if(k<n) FWT(V,f[k],1);
	}
	cout<<f[n][V-1]<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	signed T=1;
//	cin>>T;
	while(T--) solve();
	return 0;
}