题解
- 首先推出状压dp形式，然后将dp方程中分母处的当前状态人口的总和这一项移到等式左边，会发现dp方程形成一个“自己等于自己卷人口”的形式，然后子集卷积刚好可以解决。
- 注意子集卷积枚举两边1的个数时人口数组必须至少有一个1才能正确转移，不能同层转移。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i, s, t) for(int i = s, __ = t; i <= __; ++i)
#define dwn(i, s, t) for(int i = s, __ = t; i >= __; --i)
const int INF = 2147483647;
const int MAXN = 31;
const int MAXM = 100 + 2500000;
const int MOD = 998244353;
using namespace std;
inline int read(int x = 0, int f = 1){
char ch = getchar();
for(; !isdigit(ch); ch = getchar())if(ch == '-')f = -1;
for(; isdigit(ch); ch = getchar())x = ch - '0' + x * 10;
return x * f;
}
inline void write(int x){
if(x >= 10)write(x / 10); putchar(x % 10 + '0'); return ;
}
inline int add(int x, int y){x += y; return x >= MOD ? x - MOD : x;}
inline int sub(int x, int y){x -= y; return x < 0 ? x + MOD : x;}
inline void inc(int &x, int y){x += y, x -= x >= MOD ? MOD : 0; return ;}
inline void dec(int &x, int y){x -= y, x += x < 0 ? MOD : 0; return ;}
inline int mul(int x, int y){return (ll)x * y % MOD;}
inline int fpow(int x, int y, int tmp = 1){
while(y){if(y & 1)tmp = mul(tmp, x); x = mul(x, x), y >>= 1;} return tmp;
}
inline int inv(int x){return fpow(x, MOD - 2);}
inline int die(int x, int y){return (ll)x * inv(y) % MOD;}
int n, m, p, lim, num = -1, fs[MAXN], q[MAXN];
struct List{int u, v;
void get(){u = read(), v = read(); return ;}
}Edge[MAXN * MAXN >> 1];
int f[MAXN], can[MAXM], vis[MAXN], du[MAXN];
int s[MAXN][MAXM], dp[MAXN][MAXM], bc[MAXM], sum[MAXM];
int find(int x){return f[x] == x ? x : find(f[x]);}
int check(int now, int rec = 0){
rep(i, 1, n)vis[i] = (now >> i - 1) & 1;
rep(i, 1, n)du[i] = 0, f[i] = i, rec = vis[i] ? i : rec;
if(bc[now] != 1)rep(i, 1, n)inc(sum[now], vis[i] * q[i]);
rep(i, 1, m)if(vis[Edge[i].u] && vis[Edge[i].v]){
du[Edge[i].u]++, du[Edge[i].v]++;
f[find(Edge[i].u)] = f[find(Edge[i].v)];
}
rep(i, 1, n)if(vis[i])
if((find(i) != find(rec)) || (du[i] % 2))return 1;
return 0;
}
void fmt(int *u, int tag){
for(int i = 1; i < lim; i <<= 1)rep(j, 0, lim)
if(i & j)inc(u[j], ~tag ? u[j - i] : sub(0, u[j - i]));
return ;
}
void init(){
memset(fs, -1, sizeof(fs));
n = read(), m = read(), p = read();
lim = (1 << n) - 1;
rep(i, 1, m)Edge[i].get(); rep(i, 1, n)q[i] = read();
rep(now, 1, lim)bc[now] = bc[now >> 1] + (now & 1);
rep(now, 1, lim)can[now] = check(now);
rep(now, 0, lim){
sum[now] = fpow(sum[now], p);
if(can[now])s[bc[now]][now] = sum[now];
sum[now] = inv(sum[now]);
}
return ;
}
void work(){
rep(now, 0, lim)dp[1][now] = (bc[now] == 1) * can[now];
rep(i, 1, n)fmt(s[i], 1);
dp[0][0] = 1, fmt(dp[0], 1); fmt(dp[1], 1);
rep(i, 2, n){
rep(j, 0, i - 1)rep(now, 0, lim)
inc(dp[i][now], mul(dp[j][now], s[i - j][now]));
fmt(dp[i], -1);
rep(now, 0, lim)if(bc[now] != i)dp[i][now] = 0;
else dp[i][now] = mul(dp[i][now], sum[now]);
if(i != n)fmt(dp[i], 1);
}
write(dp[n][lim]); return ;
}
int main(){
init(); work(); return 0;
}