跳转至

Welcome to Liam's Blog

  • 分类于 Geometry
  • 需要 1 分钟阅读时间

\(\sin/\cos(\alpha+\beta)\) 的展开证明

图

\[ \begin{aligned} \cos(α+β) &= OB \\ & = OD - BD \\ & = OD - EC \\ & = OC \cos \beta - AC \sin \beta \\ & = OA \cos \alpha \cos \beta - OA \sin \alpha \sin \beta \\ & = \cos \alpha \cos \beta - \sin \alpha \sin \beta \end{aligned} \]
\[ \begin{aligned} \sin(α+β) &= AB \\ & = AE + BE \\ & = AE + CD \\ & = AC \cos \beta + OC \sin \beta \\ & = OA \sin \alpha \cos \beta + OA \cos \alpha \sin \beta \\ & = \sin \alpha \cos \beta + \cos \alpha \sin \beta \\ \end{aligned} \]
  • 分类于 Poly
  • 需要 5 分钟阅读时间

\(\rm FWT\) (Fast Walsh Transform) 学习笔记

本文中使用 \(\cap\) 表示按位与，用 \(\cup\) 表示按位或

与/或 卷积

问题引入

给定长度为 \(2^n\) 的数列 \(A,B\)，求 \(C_i = \sum_{j \cup k = i} A_j \times B_k\)

显然有 \(O(4^n)\) 的暴力

正变换

这一部分可以参考 FMT 中的 Zeta 变换 ，即定义 \(\hat A_i\) 为序列 \(A\) 中 \(i\) 的子集和

快速变换

考虑分治

对于长度为 \(2^n\) 的待求解的 \(\hat A\)，我们把它分成独立的两部分，即 \([0,2^{n-1})\) 和 \([2^{n-1},2^n)\) 两个区间分别求解

然后考虑这两个区间之间的贡献，发现只有 \([0,2^{n-1})\) 对 \([2^{n-1},2^n)\) 有贡献，于是对于 \(i \in [0,2^{n-1})\)，将 \(\hat A_{i}\) 加到 \(\hat A_{i+2^{n-1}}\) 中即可

时间复杂度 \(O(n 2^n)\)

  • 分类于 Poly
  • 需要 3 分钟阅读时间

FMT(Fast Möbius Transform) 学习笔记

小 Tips：在计算机语言中 \(\cap\) = & / and， \(\cup\) = | / or

定义

定义长度为 \(2^n\) 的序列的 and 卷积 \(A = B * C\) 为 \(A_i=\sum_{j \cap k = i}{B_j \times C_k}\)

考虑快速计算