集合幂级数
题单介绍
关于 FMT 与 FWT 的原理,可以参考 [rsy 的题单描述](https://www.luogu.com.cn/training/275211),学员分享的时候云浅也会再次讲解。
不在洛谷中的题目会用链接标出。
一道题目可能同时被分到多个分区内,这表示这道题目可以用多种方法解决。
-----------
FMT&FWT 基础应用:
- P4717, ABC212H, CF449D, CF662C, ABC288G, P3175, [CF103202M](https://codeforces.com/gym/103202/problem/M), [TopCoder11469](https://vjudge.net/problem/TopCoder-11469)
稍微难一点的:
- AGC034F, CF850E, P9131(请大家用 $O(m2^m)$ 解法通过), [QOJ5019](https://qoj.ac/problem/5019)
一类计算 $\prod_{i=1}^n\sum_{j=0}^{k-1}w_jx^{a_{i,j}}$(每个多项式的系数都是一样的,只是非零项的位置不同)的技巧:
- CF449D, [UOJ310](https://uoj.ac/problem/310), CF1119H, P7526(的 $98$ 分)
$k$ 进制下的 FWT(即高维 FFT):
- CF1103E(这题我不会)
「不定长的 FWT」:(我也没啥太深刻的理解,这是 rsy 告诉我的)
- [CF102129A](https://codeforces.com/gym/102129/problem/A), P8970
子集卷积基础应用:
- P3349(虽然也可以容斥), CF914G, P6097, P6570&[LOJ154](https://loj.ac/p/154)(直接做复杂度是 $O(w^32^w)$,大概是过不去的)
半半在线卷积:
- P4221, P6846, [UOJ94](https://uoj.ac/problem/94)&P6570&U280360(直接硬上半半在线卷积可能过不去), P9131
集合不交并卷积的 exp/ln:
- [UOJ94](https://uoj.ac/problem/94), P6570, U280360, [LOJ154](https://loj.ac/p/154)
杂一点的题:
- P8292(虽然可以用容斥), P5406(结合 Matrix-Tree 定理)
- ARC158F(其实大部分和 FMT 没关系,只是我比较蠢萌所以最后硬上了一个 FMT)
- 给 ABC236Ex 爆标