【FWT|【LOJ #2340】【WC 2018】—州区划分（子集卷积+状压dp）】传送门
令 f ( s ) f(s) f(s)表示状态为 s s s的人口之和， g ( s ) g(s) g(s)为状态 s s s的所有州的划分的满意度之和
则
g ( s ) = ∑ i ? s f ( i ) f ( s ) g ( s ? i ) g(s)=\sum_{i\subseteq s}\frac{f(i)}{f(s)}g(s\bigoplus i) g(s)=∑i?s?f(s)f(i)?g(s?i)
= 1 f ( s ) ∑ i ? s f ( i ) g ( s ? i ) \ \ \ \ \ \ \ \ =\frac{1}{f(s)}\sum_{i\subseteq s}f(i)g(s\bigoplus i)=f(s)1?∑i?s?f(i)g(s?i)
后面一坨是一个子集卷积的形式
直接枚举子集是 3 n 3^n 3n无法接受
用子集卷积做到 O ( n 2 2 n ) O(n^22^n) O(n22n)
欧拉回路用并查集判一下就可以了
#include
using namespace std;
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define re register
#define pb push_back
#define cs const
#define pii pair
#define fi first
#define se second
#define ll long long
cs int mod=998244353;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;
}
inline void Add(int &a,int b){(a+=b)>=mod?(a-=mod):0;
}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;
}
inline void Dec(int &a,int b){(a-=b)<0?(a+=mod):0;
}
inline int mul(int a,int b){return 1ll*a*b>=mod?1ll*a*b%mod:a*b;
}
inline void Mul(int &a,int b){a=mul(a,b);
}
inline int ksm(int a,int b,int res=1){
for(;
b;
b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));
return res;
}
inline void chemx(ll &a,ll b){ab?a=b:0;
}
cs int N=22,C=(1< 推荐阅读
- 主席树|191101CSP模拟题解
- 状压dp|[WC2018]州区划分
- 模板|FWT 模板
- bzoj1076: [SCOI2008]奖励关
- c++|loj2340 WC2018 州区划分 状压dp+FWT
- FWT|[LOJ]#2340. 「WC2018」州区划分 FWT+欧拉回路
- loj|[loj2340][FWT][子集卷积]州区划分