Description
传送门【loj|[loj2340][FWT][子集卷积]州区划分】题解
看懂题需要一会…
朴素的dp就可以列出一个方程
f [ m a s k ] = 1 r [ i ] p ∑ j ∣ k = m a s k f [ j ] ? r [ k ] p f[mask]=\frac{1}{r[i]^p}\sum_{j|k=mask} f[j]*r[k]^p f[mask]=r[i]p1?j∣k=mask∑?f[j]?r[k]p
其中 r [ i ] r[i] r[i]表示 i i i状态下的人数
那么暴力枚举子集就是 3 n 3^n 3n的噜
然后发现这其实是一个裸的子集卷积
于是就可以直接卷一下完事了…
#include
#include
#include
#include
#include
#include
#include
#include
#include
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- FWT|【LOJ #2340】【WC 2018】—州区划分(子集卷积+状压dp)
- 状压dp|[WC2018]州区划分
- 模板|FWT 模板
- BZOJ|[UOJ#348][WC2018]州区划分(状压dp+FMT)
- c++|loj2340 WC2018 州区划分 状压dp+FWT
- FWT|[LOJ]#2340. 「WC2018」州区划分 FWT+欧拉回路