Luogu

LOJ

分析

每个集合是否合法很容易判，先把这个东西预处理出来，记为 $chk_S$ 。

设 $f_S$ 表示集合 $S$ 的答案，那么有：
$$
f_S = \left( \frac{1}{W_S} \right)^p \sum_{T\subseteq S} f_T \times (W_{S - T})^p \times chk_{S - T}
$$
子集卷积即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define popcount __builtin_popcount
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=21+1,L=1<<21;
const int mod=998244353;

inline void add(int& x,int y) { x=(x+y)%mod; }

int n,m,p,lim;
int G[N],deg[N],lg[L],chk[L];
int f[N][L],w[N][L];
int val[N],sum[L],isum[L];

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

inline void FWT(int* A,int n,int op) {
    for (re int i=1;i<n;i<<=1)
        for (re int j=0;j<n;j+=(i<<1))
            for (re int k=0;k<i;++k)
                add(A[j+k+i],(op*A[j+k]+mod)%mod);
}

int fa[N];
inline int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); }
inline void merge(int x,int y) {
    x=find(x),y=find(y);
    if (x!=y) fa[x]=y;
}

inline int check(int S) {
    if (popcount(S)==1) return 0;
    for (re int i=0;i<n;++i) fa[i]=i,deg[i]=0;
    for (re int i=0;i<n;++i)
        if (S&(1<<i)) deg[i]=popcount(G[i]&S);
    for (re int i=0;i<n;++i)
        if (S&(1<<i)) {
            int x=S&G[i];
            while (x) merge(i,lg[x&-x]),x-=x&-x;
        }
    for (re int i=0;i<n&&!chk[S];++i)
        if ((deg[i]&1)||((S&(1<<i))&&deg[i]==0)) return 1;
    int s=0;
    for (re int i=0;i<n&&!chk[S];++i)
        if (S&(1<<i)&&fa[i]==i) ++s;
    if (s>1) return 1;
    return 0;
}

int main() {
    n=read(),lim=1<<n,m=read(),p=read();
    for (re int i=2;i<lim;++i) lg[i]=lg[i>>1]+1;
    for (re int i=1;i<=m;++i) {
        int u=read()-1,v=read()-1;
        G[u]|=(1<<v),G[v]|=(1<<u);
    }
    for (re int i=0;i<n;++i) val[i]=read();

    for (re int i=0;i<lim;++i) chk[i]=check(i);
    for (re int i=0;i<lim;++i) {
        for (re int j=0;j<n;++j)
            if (i&(1<<j)) sum[i]+=val[j];
        sum[i]=qpow(sum[i],p),isum[i]=qpow(sum[i],mod-2);
        if (chk[i]) w[popcount(i)][i]=sum[i];
    }

    f[0][0]=1; FWT(f[0],lim,1);
    for (re int i=1;i<=n;++i) FWT(w[i],lim,1);
    for (re int i=1;i<=n;++i) {
        for (re int j=0;j<i;++j)
            for (re int k=0;k<lim;++k)
                add(f[i][k],1ll*f[j][k]*w[i-j][k]%mod);
        FWT(f[i],lim,-1);
        for (re int j=0;j<lim;++j) f[i][j]=1ll*f[i][j]*isum[j]%mod;
        FWT(f[i],lim,1);
    }
    FWT(f[n],lim,-1); printf("%d\n",f[n][lim-1]);

    return 0;
}