WC2018 州区划分

见这个人讲得很明白

集合并卷积裸题，然而我并不会 fast subset transform（倒是会各种各样的 fst）

于是跟 shing 学了一波 fwt 的高级技巧

枚举一下并集里的元素数量，然后直接当或卷积做就可以了，最后答案 $f(n,all)$ 正好是集合并卷积卷出来的结果

#include <bits/stdc++.h>
#define LL long long
#define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
inline int read() {
    int x = 0, f = 1; char ch;
    for (ch = getchar(); !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
    for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0';
    return x * f;
}
const int maxn = 200010, mod = 998244353;
inline int inc(int x, int y) {x += y;if(x >= mod)x -= mod;return x;}
inline int dec(int x, int y) {x -= y;if(x < 0)x += mod;return x;}
inline int ksm(int x, int t) {
    int res = 1;
    while(t) {
        if(t & 1)res = 1LL * res * x % mod;
        x = 1LL * x * x % mod;
        t = t >> 1; 
    } return res;
}
inline void fwt(int *a, int n, int f) {
    for(int i=1;i<n;i<<=1)
        for(int j=0;j<n;j+=(i<<1))
            for(int k=0;k<i;++k) {
                    int x = a[j + k], y = a[i + j + k];
                    if(f == 1) a[i + j + k] = inc(x, y);
                    else a[i + j + k] = dec(y, x);
                }
}
int n, m, p, w[50], g[25][(1 << 21) + 5], f[25][(1 << 21) + 5], inv[(1 << 21) + 5], sum[(1 << 21) + 5];
struct Edge {int u, v;}es[500];
int fa[25], ind[25];
inline int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
int main() {
    n = read(), m = read(), p = read();
    rep(i, 1, m) es[i].u = read(), es[i].v = read();
    rep(i, 1, n) w[i] = read(); int MAXSTATE = (1 << n) - 1;
    rep(s, 0, MAXSTATE) {
        rep(i, 1, n) fa[i] = i; memset(ind, 0, sizeof(ind));
        int bsize = __builtin_popcount(s);
        rep(i, 1, n) if(s & (1 << (i-1))) sum[s] += w[i]; inv[s] = ksm(sum[s], mod - 2);
        rep(i, 1, m) if((s & (1 << (es[i].u - 1))) && (s & (1 << (es[i].v - 1)))) {
            int fu = find(es[i].u), fv = find(es[i].v);
            ind[es[i].v]++; ind[es[i].u]++;
            if(fu == fv) continue; fa[fu] = fv; bsize--;
        }
        int hs = 0;
        rep(i, 1, n) if(s & (1 << (i - 1))) if(ind[i] & 1) hs = 1;
        if(bsize > 1 || hs) g[__builtin_popcount(s)][s] = ksm(sum[s], p);
    }
    f[0][0] = 1;
    fwt(f[0], MAXSTATE+1, 1);
    rep(i, 0, n) fwt(g[i], MAXSTATE+1, 1);
    rep(i, 1, n) {
        rep(j, 1, i) rep(s, 0, MAXSTATE) (f[i][s] += (1LL * g[j][s] * f[i - j][s] % mod)) %= mod;
        fwt(f[i], MAXSTATE+1, -1);
        rep(s, 0, MAXSTATE) f[i][s] = 1LL * f[i][s] * ksm(inv[s], p) % mod;
        if(i < n) fwt(f[i], MAXSTATE+1, 1);
    }
    cout << f[n][MAXSTATE] << endl;
}