传送门
题解： 显然的DP ： g[S]f[S]=∑i∈Sf[S⊕i]g[i] g [ S ] f [ S ] = ∑ i ∈ S f [ S ⊕ i ] g [ i ] 。
不会做，可以考虑加一个状态优化掉子集转移。
记 f[i][S] f [ i ] [ S ] 表示有 i i 个城市被选，按位或之后为SS，那么可以去除子集转移的限制，因为 f[n][U] f [ n ] [ U ] 肯定是每个城市恰好选择一次。 然后枚举 i i 做FMTFMT就可以了，时间复杂度 O(n22n) O ( n 2 2 n )
#include <bits/stdc++.h> typedef long long LL; using namespace std; const int N=(1<<21)+50; const int mod=998244353; int n,m,p,k,f[22][N],g[22][N],sum[N],inv[N]; int w[22],bin[22]; vector <int> edge[22]; inline int mul(int x,int y) {return (LL)x*y%mod;} inline int add(int &x,int y) {x=(x+y>=mod)?x+y-mod:x+y;} inline int power(int a,int b) { int rs=1; for(;b;b>>=1,a=mul(a,a)) if(b&1) rs=mul(rs,a); return rs; } int deg[22],anc[22],ch[22],fir; inline int getanc(int a) {return (anc[a]==a)?a:(anc[a]=getanc(anc[a]));} inline bool check(int sta) { fir=-1; for(int i=0;i<n;i++) deg[i]=0,anc[i]=i,ch[i]=(sta&bin[i]); for(int i=0;i<n;i++) { if(!ch[i]) continue; for(int j=0;j<edge[i].size();++j) { int v=edge[i][j]; if(!ch[v])continue; ++deg[i]; ++deg[v]; anc[getanc(i)]=getanc(v); } } for(int i=0;i<n;i++) if(ch[i] && getanc(i)==i){ if(fir==-1) fir=i; else return true; } for(int i=1;i<=n;i++) if(ch[i] && (deg[i]&1)) return true; return false; } inline void fmt(int *f) { for(int i=1;i<k;i<<=1) for(int j=0;j<k;j++) if(i&j) add(f[j],f[j^i]); } inline void dfmt(int *f) { for(int i=1;i<k;i<<=1) for(int j=0;j<k;j++) if(i&j) add(f[j],mod-f[j^i]); } int main() { scanf("%d%d%d",&n,&m,&p); k=1<<n; for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); edge[x-1].push_back(y-1); } for(int i=0;i<n;i++) scanf("%d",&w[i]),bin[i]=(1<<i); for(int i=0;i<k;i++) { int cnt=0; for(int j=0;j<n;j++) if(i&bin[j]) add(sum[i],w[j]),++cnt; sum[i]=power(sum[i],p); if(!check(i)) g[cnt][i]=0; else g[cnt][i]=sum[i]; inv[i]=power(sum[i],mod-2); } f[0][0]=1; fmt(f[0]); for(int i=1;i<=n;i++) fmt(g[i]); for(int i=1;i<=n;i++) { for(int j=0;j<i;j++) for(int s=0;s<k;++s) add(f[i][s],mul(f[j][s],g[i-j][s])); dfmt(f[i]); for(int s=1;s<k;++s) f[i][s]=mul(f[i][s],inv[s]); fmt(f[i]); } dfmt(f[n]); printf("%d\n",f[n][k-1]); }