$\Huge\text{qndmx}$
by zzy2333 @ 2019-12-26 13:51:32
金钩萌新
by iotang @ 2019-12-26 14:18:02
@[EternalAlexander](/user/48355) Orz EA /qq
by disangan233 @ 2019-12-26 14:30:29
~~吸氧~~
by cmll02 @ 2020-02-02 15:17:58
卡常火车头不好嘛？
```cpp
#include <bits/stdc++.h>
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define ll long long
const int mod=998244353;
int n,m,p,u[515],v[515],w[23],degr[23],sum[1<<22],f[23][1<<22],ok[1<<22],g[23][1<<22],inv[1<<22],size[1<<22];
namespace dsu {
int fa[25];
void reset(){std::memset(fa,0,sizeof(fa));}
int getf(int x){return fa[x]?fa[x]=getf(fa[x]):x;}
int merge(int x,int y){
int f1=getf(x),f2=getf(y);
if (f1==f2)return 0;
fa[f2]=f1;return 1;
}
}
inline int dec(int x){return x>=mod?x-mod:x;}
int qpow(int a,int b)
{
if(b==0)
return 1;
int d=qpow(a,b>>1);d=(ll)d*d%mod;
if (b&1)d=(ll)d*a%mod;
return d;
}
int check(int S){
int cnt=__builtin_popcount(S);
dsu::reset();
std::memset(degr,0,sizeof(degr));
for(int i=1;i<=m;++i)
if (((S>>(u[i]-1))&1)&&((S>>(v[i]-1))&1)){
degr[u[i]]++;degr[v[i]]++;
cnt-=dsu::merge(u[i],v[i]);
}
if (cnt>1)return 1;
for(int i=1;i<=n;++i)if(degr[i]%2)
{
return 1;
}
return 0;
}
void fwt(int *a,int len,int flag)
{
for(int i=1;i<len;i<<=1)
for(int j=0;j<len;j+=i*2)
for(register int k=0;k<i;++k){
if(flag==1)a[j+k+i]=dec(a[j+k+i]+a[j+k]);
else a[j+k+i]=dec(a[j+k+i]-a[j+k]+mod);
}
}
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=m;++i)scanf("%d%d",&u[i],&v[i]);
for(int i=1;i<=n;++i)scanf("%d",&w[i]);
for(int S=0;S<(1<<n);++S){
ok[S]=check(S);
size[S]=__builtin_popcount(S);
for(int i=1;i<=n;++i)if((S>>(i-1))&1){sum[S]=(sum[S]+w[i])%mod;}
sum[S]=qpow(sum[S],p);
g[size[S]][S]=ok[S]?sum[S]:0;
inv[S]=qpow(sum[S],mod-2);
}
for(int i=0;i<=n;++i)fwt(g[i],1<<n,1);
f[0][0]=1;
for(int i=1;i<=n;++i){
fwt(f[i-1],1<<n,1);
for(int j=0;j<i;++j)
for(int k=0;k<(1<<n);++k)
f[i][k]=dec(f[i][k]+(ll)f[j][k]*g[i-j][k]%mod);
fwt(f[i],1<<n,-1);
for(int j=0;j<(1<<n);++j)f[i][j]=size[j]==i?(ll)f[i][j]*inv[j]%mod:0;
}
printf("%d",f[n][(1<<n)-1]);
return 0;
}
```
by 103PA @ 2020-05-25 20:58:02