133F
(离线做法)ABC133F 题解
### (离线做法)ABC133F 题解 题目链接:[ABC133F](https://www.luogu.com.cn/problem/AT_abc133_f) #### 明确维护目标 显然我强制修改强制查询的在线做法会超时,于是我考虑离线做法。 首先我们可以知道,树上的路径可以用和差关系线性表示 ......
ARC133F FWT 做法
看见网上题解都是“二维生成函数”,就来传一下这个做法( 问题可以转化为:$n$ 枚硬币,每次随机翻一枚,求最后正面朝上硬币个数的期望。 把这个过程看作 XOR 卷积,并且需要卷积的两个数组有特性:在 popcount 相同的位置值相同。 这样只要对这种特殊的数组能做 fwt 就做完了。 于是现在要解 ......