Welcome to Liam's Blog
CF1267H Help BerLine
题意
已知有 \(n \le 8500\) 个基地，以及开启它们的顺序排列 \(p\)，初始所有基地都关闭。
求一个整数序列 \(f\) 使得在任意时刻，已开启的基地的 \(f\) 值按顺序排成的序列满足：
-
任意子段都有一个只出现在其中过一次的值（以下记为合法）
-
\(\forall i, f_i \in [1,24]\)
FFT & NTT 复习笔记
默认文中的形如 \([l,r)\) 的区间为其与整数集的交集。
快速变换
设原多项式为 \(F(x) = \sum_{i \in [0,n)} a_i x ^ i\)，其中 \(n = 2 ^ k, k \in \mathbb Z ^ +\)。
我们要求 \(\forall i \in [0,n),\hat a_i = F(t_i)\)，其中 \(t\) 是一个长度为 \(n\) 且两两互不相同的序列。
显然 \(F\) 可以被一组 \(\hat a,t\) 唯一确定，即点值表示法。
平面直角坐标系的点绕原点旋转公式及证明
设点 \(A(x,y)\) 绕原点 \(O(0,0)\) 逆时针旋转 \(\beta\)，则设在极坐标系下 \(A\) 的坐标为 \((r,\alpha)\)
这意味着 \(x=r \cos \alpha, y=r \sin \alpha\)
目标点 \(A'(x',y')\) 的极坐标即为 \((r,\alpha + \beta)\)
展开（其中 \(\sin\) 和 \(\cos\) 的展开参考 here）：
\(\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}
\]
\(\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)\)
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}\)
考虑快速计算