集合幂级数

题单介绍

关于 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 爆标

题目列表

  • 【模板】快速莫比乌斯 / 沃尔什变换 (FMT / FWT)
  • [ABC212H] Nim Counting
  • Jzzhu and Numbers
  • Binary Table
  • [ABC288G] 3^N Minesweeper
  • [HAOI2015] 按位或
  • [AGC034F] RNG and XOR
  • Random Elections
  • [USACO23FEB] Problem Setting P
  • Triple
  • Virtual Self
  • Radix sum
  • 宿命 | Regulation of Destiny
  • [ZJOI2016] 小星星
  • Sum the Fibonacci
  • 【模板】子集卷积
  • [NOI Online #3 提高组] 优秀子序列
  • [WC2018] 州区划分
  • [CEOI 2019] Amusement Park
  • 天空度假山庄
  • [省选联考 2022] 卡牌
  • [THUPC 2019] 找树
  • [ARC158F] Random Radix Sort
  • [ABC236Ex] Distinct Multiples