Skip to main content

洛谷 P4717 【模板】快速莫比乌斯 / 沃尔什变换 (FMT / FWT)

给定长度为 2n2^n 的两个序列 A,BA,B,设:

Ck=ij=kAi×BjC_k=\sum_{i\oplus j=k}A_i\times B_j

分别当 \oplusor,and,xor\operatorname{or},\operatorname{and},\operatorname{xor} 时求出 CC