传送门
题解：
显然的DP ： g[S]f[S]=∑i∈Sf[S⊕i]g[i]g [ S ] f [ S ] = ∑ i ∈ S f [ S ⊕ i ] g [ i ] 。
不会做，可以考虑加一个状态优化掉子集转移。
【UOJ#348. [WC2018]州区划分（FMT）】记 f[i][S]f [ i ] [ S ] 表示有 ii 个城市被选，按位或之后为 SS ，那么可以去除子集转移的限制，因为 f[n][U]f [ n ] [ U ] 肯定是每个城市恰好选择一次。 然后枚举 ii 做 FMTF M T 就可以了，时间复杂度 O(n22n)O ( n 2 2 n )
#include
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 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 
