CF383E Vowels
Codeforces 分析 这个数量平方的异或和感觉没有什么性质，那么我们只能想办法对每个集合求出数量。 一个想法是先预处理出集合大小为 $1$ 时的数量，然后做子集和，但是这样子会算重：对于 $abc$，$ab$ 处将其计算了两次。 于是考虑容斥：我们在 $a, b, c$ 处加 $1$，$ab, ac, bc$ 处减 $1$、$abc$ 处加 $1$，那么这样子做子集和求出来的数量就是正...
标签 FWT 下的文章
- 首页
- FWT
洛谷5406 [THUPC2019]找树
Luogu LOJ 分析 转化为计数问题，求每种权值的生成树个数。 考虑矩阵树定理 我们对每条边构造一个多项式 $f(x)=x^w$，并将乘法定义为输入的运算，这样子求出的基尔霍夫矩阵删去一行一列后的行列式的 $x^w$ 项系数即为边权和为 $w$ 的生成树个数。 具体实现时，我们先对行列式中的每个元素做 FWT，求出行列式后再 IFWT 回来。这里的 FWT 和 IFWT 是广义的，即这...
CF908H New Year and Boolean Bridges
Codeforces Luogu 分析 显然满足 $G_{i,j}=\mathsf{A}$ 的 $i,j$ 在同一个强连通分量内，所以先把这些点并起来。那么如果一个强连通分量内有 XOR 边就是不合法的。 显然每个强连通分量内成环最优，那么答案等于 $n-1+$点数 $\geq 2$ 的强连通分量个数，则应最小化后面那个东西，即把一些强连通分量在满足条件的情况下合并成一个大环。 因为点数 $...
洛谷5366 [SNOI2017]遗失的答案
Luogu LOJ 分析 首先特判掉 $G\nmid L$ 的情况。 为了方便，将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数，必须选 $X$，选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。 我们先不管那个必须选 $X$ 的条件，想一想怎么做。 注意到值域只有 $10^8$，即最多只有 $8...
JOI 2018 Final 简要题解
寒冬暖炉 同 CF1110B Tape。 先令每个客人来的时刻都开暖炉，其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。 代码 美术展览 显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。 设 $sum_i$ 表示 $\sum_{j=1}^iB_j$，那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。 因此我们从后往前扫，维护 ...
CF662C Binary Table
Codeforces 分析 设 $S_i$ 表示第 $i$ 列的状态，$F_i$ 表示 $i$ 状态翻转或不翻转最少能有多少个 $1$ 。 首先考虑一个暴力：枚举翻转哪几行。那么答案就是 $\displaystyle\min_{X}\left\{\sum_{i=1}^mF_{S_i\oplus X}\right\}$。 里面考虑枚举 $S_i\oplus X$，那么答案就是 $\displa...
洛谷4221 [WC2018]州区划分
Luogu LOJ 分析 每个集合是否合法很容易判，先把这个东西预处理出来，记为 $chk_S$ 。 设 $f_S$ 表示集合 $S$ 的答案，那么有： 子集卷积即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==========...
洛谷3175 [HAOI2015]按位或
Luogu 分析 我们把每个数看成一些二进制位的集合，每一位的值是加入的时间。那么我们要求的是全集的 $\max$ 值。 考虑 min-max 容斥 那么只需要求子集和，可以 FMT。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==...