0基础FWT详解2(巩固)

FWT巩固1

在 上篇文章 中，我们学习了 $FWT$，本文将带读者一起做几道题，巩固对 $FWT$ 的使用

卡常技巧

一个常数大的 $FWT$ 是非常不利于做题的，所以我们需要卡常。

作者简单总结了一下几点：

1. 能不取模就不取模，取模是非常慢的运算。
2. 能不开 long long 就不开。
3. 对于固定的小于模数用乘法代替取模。
4. 循环展开。

对于第三点，我们使用一种叫 Barrett Reduction 的方法。

这里偷个懒，直接上图片：

代码实现：

const int mod = 1e9 + 7;
const uint64_t m = (1ULL << 64) / mod;  // 预计算 m// Barrett Reduction 计算 x % mod
uint32_t barrett_reduce(uint64_t x) {uint64_t q = ((__uint128_t(x) * m) >> 64);  // q ≈ floor(x / mod)uint32_t r = x - q * mod;                  // r = x - q * modreturn r < mod ? r : r - mod;              // 调整到 [0, mod)
}

当然有时候不用那么大，可以简化，不一定要用 __uint128_t 类型防止溢出。

巩固习题

luogu6097

link

给定两个长度为 $2^n$ 的序列 $a_0,a_1,\cdots ,a_{2^n-1}$ 和 $b_0,b_1,\cdots ,b_{2^n-1}$，你需要求出一个序列 $c_0,c_1,\cdots ,c_{2^n-1}$，其中 $c_k$ 满足：

$$c_k=\sum _{\begin{array}{c}i\&j=0\\ i\mid j=k\end{array}}{a}_i{b}_j$$

其中$\mid$表示按位或，$\&$表示按位与。

答案对 $10^9+9$ 取模。

注意到第二个就是按位或卷积，第一个则是要求 $|i|+|j|=|i|j|$，其中 $|x|$ 为 $x$ 在二进制下 $1$ 的个数。

我们再开一维记录集合中的元素个数即可。

具体地，$a_i\to a_{|i|,i},b_i\to b_{|i|,i}$，然后对每个 $i$ 进行一次 $FWT$，最后可得 $c_{i,o}={\sum }_{j=0}^{i}a$