题解
学习一个全世界人都会只有我不会的东西
子集变换！
难道我要把这题当板子讲？等等这题好像是板。。。WC出板题好刺激啊= =
假装我们都做过HAOI2015的FMT题，我们都知道一些FMT怎么解决或卷积的理论（似乎FMT本质就是FWT的或卷积方式）
子集变换是什么呢，就是把FMT带一个多项式
什么意思呢，就是我们需要
(h_{S} = sum_{T subseteq S} g_{T}f_{S - T})
算h，怎么算，显然或卷积不成立啊，因为可能有交集
那么考虑到(|S| + |S - T| = |S|)绝对值符号指元素个数，也就是1的个数
我们就……套上一个多项式！
(g_{T}x^{|T|})的(g_{T})是有值的
这样我们对每个N都做一遍FMT，相乘之后做一遍IFMT，我们需要的就是(h_{S}x^{|S|})
那么……我们再来看这道题
显然就是
(dp_{S} = frac{1}{g_{S}}sum_{T subseteq S}g_{T}dp_{S - T})
g就是集合里人数的总和的p次方
啥，自己和自己卷积……
我们处理的时候从dp[1 - N][S]开始处理，就是每次算好每一层的dp值，还原回来乘上前面的系数，再FMT回去
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
//#define ivorysi
#define MAXN 100005
#define eps 1e-7
#define mo 974711
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
const int64 MOD = 998244353;
int N,M,p;
int g[25][25],ind[25],cnt[1 << 21],w[25],fa[25];
int64 F[23][1 << 21],inv[1 << 21],dp[23][1 << 21];
bool vis[25];
int getfa(int x) {
return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
int64 fpow(int64 x,int64 c) {
int64 res = 1,t = x;
while(c) {
if(c & 1) res = res * t % MOD;
t = t * t % MOD;
c >>= 1;
}
return res;
}
int64 calc(int64 v) {
if(p == 0) return 1;
else if(p == 1) return v;
else return v * v % MOD;
}
void FMT(int64 *a,int64 ty) {
for(int i = 1 ; i < (1 << N) ; i <<= 1) {
for(int j = 0 ; j < (1 << N) ; ++j) {
if(j & i) a[j] = (a[j] + ty * a[j ^ i] + MOD) % MOD;
}
}
}
void Init() {
scanf("%d%d%d",&N,&M,&p);
int u,v;
for(int i = 1 ; i <= M ; ++i) {
scanf("%d%d",&u,&v);
g[u][v] = g[v][u] = 1;
}
for(int i = 1 ; i <= N ; ++i) scanf("%d",&w[i]);
for(int i = 1 ; i < (1 << N) ; ++i) cnt[i] = cnt[i - (i & -i)] + 1;
for(int S = 1 ; S < (1 << N) ; ++S) {
memset(vis,0,sizeof(vis));
memset(ind,0,sizeof(ind));
int sum = 0,v = 0;
for(int i = 1 ; i <= N ; ++i) {
fa[i] = i;
if((S >> i - 1) & 1) {
vis[i] = 1,sum += w[i];
if(v == 0) v = i;
}
}
for(int i = 1 ; i <= N ; ++i) {
if(!vis[i]) continue;
for(int j = i + 1 ; j <= N ; ++j) {
if(!vis[j]) continue;
if(g[i][j] == 1) {
fa[getfa(i)] = getfa(j);
++ind[i];++ind[j];
}
}
}
bool flag = 1;
for(int i = 1 ; i <= N ; ++i) {
if(vis[i]) {
if(ind[i] & 1) {flag = 0;break;}
if(getfa(v) != getfa(i)) {flag = 0;break;}
}
}
F[cnt[S]][S] = (flag ^ 1) * calc(sum);
inv[S] = fpow(calc(sum),MOD - 2);
}
}
void Solve() {
for(int i = 1 ; i <= N ; ++i) FMT(F[i],1);
dp[0][0] = 1;
FMT(dp[0],1);
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= i ; ++j) {
for(int S = 0 ; S < (1 << N) ; ++S) {
(dp[i][S] += dp[i - j][S] * F[j][S]) %= MOD;
}
}
FMT(dp[i],-1);
for(int S = 0 ; S < (1 << N) ; ++S) dp[i][S] = dp[i][S] * inv[S] % MOD;
FMT(dp[i],1);
}
FMT(dp[N],-1);
printf("%lld
",dp[N][(1 << N) - 1]);
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}