首先不难判断每个点集是否合法。
一个点集合法，当且仅当其不连通或导出子图中存在一个点的度数是奇数。
设 \(f_S\) 表示已经划分出了的州区的并集为 \(S\) 的所有方案的满意度之和，\(g_S = \begin{cases}\sum\limits_{i\in S} w_i, &S\text{ is valid}\\0, & S\text{ is invalid}\end{cases}\)。
那么显然有 \(f_S = \frac 1{\sum_{i\in S}w_i} \sum\limits_{T \subset S} f_T g_{\complement_S T}\)。
用 FWT 优化子集卷积即可，复杂度 \(O(n^2 2^n)\)（并不需要另外划分阶段做 \(n\) 次子集卷积，一边子集卷积一边转移即可）
在洛谷不开 O2 直接炸裂（
代码： 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w && (x = -x);
}
const int S = 1 << 21;
const int N = 21;
const int mod = 998244353;
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int n,m,s,p;
vector<int> e[N + 5];
int vis[N + 5],deg[N + 5],q[N + 5],head,tail;
inline void bfs(int s,int t)
{
memset(vis,0,sizeof vis),head = tail = 0;
vis[q[++tail] = t] = 1;
for(register int p;head < tail;)
{
p = q[++head];
for(register vector<int>::iterator it = e[p].begin();it != e[p].end();++it)
if(!vis[*it] && (s & (1 << *it)))
vis[*it] = 1,q[++tail] = *it;
}
}
int sum[S + 5];
int f[N + 5][S + 5],g[N + 5][S + 5];
inline void fwt(int *a,int type,int n)
{
for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
for(register int i = 0;i < n;i += w)
for(register int j = 0;j < m;++j)
a[i | j | m] = type == 1 ? add(a[i | j | m],a[i | j]) : dec(a[i | j | m],a[i | j]);
}
int main()
{
read(n),read(m),read(p),s = 1 << n;
int u,v;
for(register int i = 1;i <= m;++i)
read(u),read(v),--u,--v,e[u].push_back(v),e[v].push_back(u);
for(register int i = 0;i < n;++i)
read(sum[1 << i]);
for(register int i = 1,t,flag;i < s;++i)
{
sum[i] = sum[i ^ lowbit(i)] + sum[lowbit(i)],memset(deg,0,sizeof deg),flag = t = 0;
for(register int j = 0;j < n;++j)
if(i & (1 << j))
for(register vector<int>::iterator it = e[j].begin();it != e[j].end();++it)
if(i & (1 << *it))
++deg[*it];
for(register int j = 0;j < n;++j)
if(i & (1 << j))
{
!t && (t = j);
if(deg[j] & 1)
{
flag = 1;
break;
}
}
if(!flag)
{
bfs(i,t);
for(register int j = 0;j < n;++j)
if((i & (1 << j)) && !vis[j])
{
flag = 1;
break;
}
}
if(flag)
g[__builtin_popcount(i)][i] = fpow(sum[i],p);
}
for(register int i = 1;i < s;++i)
sum[i] = fpow(sum[i],mod - p - 1);
for(register int i = 0;i <= n;++i)
fwt(g[i],1,s);
f[0][0] = 1,fwt(f[0],1,s);
for(register int i = 1;i <= n;++i)
{
for(register int j = 1;j <= i;++j)
for(register int k = 0;k < s;++k)
f[i][k] = (f[i][k] + (long long)f[i - j][k] * g[j][k]) % mod;
fwt(f[i],-1,s);
for(register int j = 0;j < s;++j)
f[i][j] = (long long)f[i][j] * sum[j] % mod;
i < n && (fwt(f[i],1,s),1);
}
printf("%d\n",f[n][s - 1]);
}