【题解】「WC2018」州区划分 FST+状压 DP loj2340 —Qiuly

状压 $\rm{DP}$ 。

显然题目给出的州的不合法的条件就是这个州不存在欧拉回路，这个好办，按照欧拉回路的性质对于所有的状态相应的州预处理一下即可。

然后设 $f_S$ 表示将点集状态为 $S$ 时，这个子图的所有划分方案的满意度之和。

转移柿显然：
$$
f_S=\sum_{T\subseteq S} f_{S-T} \times \left( \frac {\sum_{x \in T} w_x} {\sum_{x \in S} w_x} \right)^p\\
f_S=\left(\frac{1}{\sum_{x \in S} w_x}\right)^p\sum_{T\subseteq S} f_{S-T} \times \left(\sum_{x \in T} w_x\right)^p\\
f_S=\left(\frac{1}{\sum_{x \in S} w_x}\right)^p\sum_{T\subseteq S} f_{S-T} \times g_{T}\\
$$
你会发现 $\rm{WC}$ 出了板子题。

$fst$ 处理一下上面的柿子即可。

Code：

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=23;
const int mod=998244353;

int n,m,p,U,w[N],fa[N],mul[N],deg[N],ok[1<<N],map[N][N];
int sum[1<<N],tot[1<<N],inv[1<<N],g[N][1<<N],f[N][1<<N];

inline int pow(int x,int y,int res=1) {
    for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
    return res;
}
int find(int x) {return fa[x]?fa[x]=find(fa[x]):x;}
inline bool pre_and_chk(int S) {
    for(int i=1;i<=n;++i) if(mul[i-1]&S) sum[S]+=w[i],++tot[S],deg[i]=fa[i]=0;
    int now_tot=tot[S];
    for(int i=1;i<=n;++i) if(mul[i-1]&S)
        for(int j=i+1;j<=n;++j) if((mul[j-1]&S)&&(map[i][j])) {
            ++deg[i],++deg[j];
            if(find(i)^find(j)) fa[find(i)]=find(j),now_tot--;
        }
    if(now_tot>1) return true;
    for(int i=1;i<=n;++i) if((mul[i-1]&S)&&(deg[i]&1)) return true;
    return false;
}

inline void FMT(int*a,short inv) {
    for(int i=1;i<mul[n];i<<=1) for(int j=0;j<mul[n];++j)
        if(j&i) (a[j]+=a[i^j]*inv)%=mod;
}

int main() {
    scanf("%d%d%d",&n,&m,&p),U=(1<<n)-1,mul[0]=1;
    for(int i=1;i<=n;++i) mul[i]=mul[i-1]<<1;
    for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),map[u][v]=map[v][u]=1;
    for(int i=1;i<=n;++i) scanf("%d",&w[i]);
    for(int i=0;i<=U;++i) ok[i]=pre_and_chk(i);
    for(int i=0;i<=U;++i) {
        sum[i]=pow(sum[i],p),inv[i]=pow(sum[i],mod-2);
        if(ok[i]) g[tot[i]][i]=sum[i];
    }
    for(int i=0;i<=n;++i) FMT(g[i],1);
    f[0][0]=1,FMT(f[0],1);
    for(int i=1;i<=n;++i) {
        for(int j=0;j<i;++j) for(int k=0;k<mul[n];++k)
            (f[i][k]+=1ll*f[j][k]*g[i-j][k]%mod)%=mod;
        FMT(f[i],-1);
        for(int j=0;j<mul[n];++j) f[i][j]=1ll*f[i][j]*inv[j]%mod;
        for(int j=0;j<mul[n];++j) if(tot[j]!=i) f[i][j]=0;
        if(i^n) FMT(f[i],1);
    }
    printf("%d\n",(f[n][U]+mod)%mod);
    return 0;
}