「WC2018」州区划分（FWT）
「WC2018」州区划分（FWT） 我去弄了一个升级版的博客主题，比以前好看多了。感谢 @Wider
不过我有阅读模式的话不知为何 \(\text{LATEX}\) 不能用，所以我就把这个功能删掉了。
洛谷上不开 \(O_2\) 根本过不去，自带大常数被卡到 \(15\) 分。。。
首先题了读了很久，发现一个州的集合可以不连通。。。
我们可以 \(O(n^22^n)\) 检验每一个状态是否满足条件，用并查集即可。
\(f[S]\) 为状态 \(S\) 时的满意度之和，\(g[S]\) 当状态 \(S\) 为合法状态时为 \(sum_S^p\)
\[f_S=\frac {1}{sum_S^p}\sum_{T\subset S}f_Tg_{S-T}\]
然后这个东西可以用 \(or\) 卷积的 \(FWT\) 优化。我觉得出题人特地把数据范围出这么大应该是卡 \(O(3^n)\) 的枚举子集。
【「WC2018」州区划分（FWT）】\(Code\ Below:\)
// luogu-judger-enable-o2
#include
using namespace std;
const int mod=998244353;
int n,m,p,lim,w[30],d[30],e[30],fa[30],bin[30],cnt[1<<21],sum[1<<21],inv[1<<21],f[22][1<<21],g[22][1<<21];
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;
}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;
}
inline int mul(int x,int y){return 1ll*x*y-1ll*x*y/mod*mod;
}inline int fpow(int a,int b){
int ret=1;
for(;
b;
b>>=1,a=mul(a,a))
if(b&1) ret=mul(ret,a);
return ret;
}inline void FWT(int *f,int n){
for(int len=1;
len>1]+(i&1);
int x,y;
for(int i=0;
i 转载于:https://www.cnblogs.com/owencodeisking/p/10450888.html
推荐阅读
- 八、「料理风云」
- 「#1-颜龙武」区块链的价值是什么（）
- 《深度倾听》第5天──「RIA学习力」便签输出第16期
- 「按键精灵安卓版」关于全分辨率脚本的一些理解（非游戏app）
- 「我的2017」——2017|「我的2017」——2017,大事件盘点
- 「适合发朋友圈的可爱短句文案」
- 「漫威之父」斯坦·李去世，回味老爷子在漫威中客串的各种角色
- 史前艺术的审美类型「清央美术」
- 「未来30年」你的孩子会成为社会精英吗（）
- 「日记」他乡，温暖的日子