Description：

给一个图划分成多个子图，要求每个子图中都不存在欧拉回路，第 $i$ 个子图的价值为第 $i$ 个子图所有点的权值和除以前 $i$ 个子图所有点的权值和的 $p$ 次方，一个划分的价值是所有子图的权值之积，问所有划分方案的价值和。

$1\leqslant n\leqslant 21$ ，无重边。

Solution：

既然 $n$ 只有 $21$ 那就可以暴力处理出所有合法的点集，复杂度 $O(2^nm)=O(2^nn^2)$ ，然后设计一个 $dp$ ： $$ f[S]=\sum_{T\subseteq S}(\frac{W[T]}{W[S]})^p[check(T)]\times f[S-T] $$ 后面的非常像一个卷积，但是却并不是子集卷积，因为 $S-T\cap T=\empty$ ，因此一个方法就是强行利用 $cnt[S-T]+cnt[T]=cnt[S]$ 分层卷积就行了。 $$ f[i][S]=\frac 1{W[S]^p}\sum_{T\subset S}g[T]\times f[i-cnt[T]][S-T](g[T]=[check(T)](\sum_{i\in T}val[i])^p) $$ 直接带着 $FMT$ 之后的数组做就可以了。

Code：

// luogu-judger-enable-o2

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,p;

#define MAXN 22

int f[MAXN][1 << MAXN];

int g[MAXN][1 << MAXN];

int check[1 << MAXN];

#define I inline

#define R register

struct edge

{

    int u,v;

}e[MAXN * MAXN];

int w[MAXN];

int deg[MAXN];

I bool bit(int s,int i){return ((s >> (i - 1)) & 1);}

I int lowbit(int x){return x & (-x);}

int cnt[1 << MAXN],val[1 << MAXN],valp[1 << MAXN],valpinv[1 << MAXN];

#define MOD 998244353

I int mul(int a,int b)

{

    R int r = a + b;

    if(r < 0)r += MOD;

    if(r >= MOD)r -= MOD;

    return r;

}

I void FMT(int f[],int l,int type)

{

    for(R int i = 1;i < l;i = i << 1)

        for(R int k = 0;k < l;++k)

            if(k & i)f[k] = mul(f[k],type * f[k ^ i]);

    return;

}

I int power(int a,int b)

{

    R int res = 1;

    while(b > 0)

    {

        if(b & 1)res = 1ll * res * a % MOD;

        a = 1ll * a * a % MOD;

        b = b >> 1;

    }

    return res;

}

int fa[MAXN];

int find(int x){return (x == fa[x] ? x : fa[x] = find(fa[x]));}

int G[MAXN][MAXN];

int main()

{

    scanf("%d%d%d",&n,&m,&p);

    for(R int i = 1;i <= m;++i)scanf("%d%d",&e[i].u,&e[i].v),++G[e[i].u][e[i].v];

    for(R int i = 1;i <= n;++i)scanf("%d",&w[i]);

    R int tot = (1 << n) - 1;

    for(R int s = 1;s <= tot;++s)

    {

        memset(deg,0,sizeof(deg));

        for(R int i = 1;i <= n;++i)fa[i] = i;

        check[s] = 0;

        for(R int i = 1;i <= n;++i)if(bit(s,i))

        {

            for(R int j = 1;j <= n;++j)if(bit(s,j))

            {

                if(G[i][j] == 0)continue;

                ++deg[i];++deg[j];

                if(find(i) != find(j))fa[find(i)] = find(j);

            }

        }

        for(R int i = 1;i <= n;++i)if(bit(s,i) && (deg[i] % 2) == 1)check[s] = 1;

        R int v = 0;

        for(R int i = 1;i <= n;++i)if(bit(s,i))if(v == 0)v = find(i);else if(find(i) != v)check[s] = 1;

        cnt[s] = cnt[s ^ lowbit(s)] + 1;

        for(R int i = 1;i <= n;++i)if(bit(s,i))val[s] += w[i];

        g[cnt[s]][s] = check[s] * power(val[s],p);

        valp[s] = power(val[s],p);valpinv[s] = power(valp[s],MOD - 2);

    }

    for(R int i = 1;i <= n;++i)FMT(g[i],tot + 1,1);

    f[0][0] = 1;FMT(f[0],tot + 1,1);

    for(R int i = 1;i <= n;++i)

    {

        for(R int j = 1;j <= i;++j)

        {

            for(R int s = 0;s <= tot;++s)f[i][s] = mul(f[i][s],1ll * g[j][s] * f[i - j][s] % MOD);

        }

        FMT(f[i],tot + 1,-1);

        for(R int s = 0;s <= tot;++s)

            if(cnt[s] != i)f[i][s] = 0;

            else f[i][s] = 1ll * f[i][s] * valpinv[s] % MOD;

        FMT(f[i],tot + 1,1);

    }

    FMT(f[n],tot + 1,-1);

    cout << f[n][tot] << endl;

    return 0;

}