LibreOJ 2340 「WC2018」州区划分

首先不难判断每个点集是否合法。
一个点集合法，当且仅当其不连通或导出子图中存在一个点的度数是奇数。

设 fS 表示已经划分出了的州区的并集为 S 的所有方案的满意度之和，gS={∑i∈Swi,S is valid0,S is invalid。
那么显然有 fS=1∑i∈Swi∑T⊂SfTg∁ST。
用 FWT 优化子集卷积即可，复杂度 O(n22n)（并不需要另外划分阶段做 n 次子集卷积，一边子集卷积一边转移即可）

在洛谷不开 O2 直接炸裂（

代码：

#include <cstdio>
#include <vector>
#include <cstring>
#define lowbit(x) ((x) & -(x))
#define add(x,y) (x + y >= mod ? x + y - mod : x + y)
#define dec(x,y) (x < y ? x - y + mod : x - y)
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
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]);
}