2024

2024年6月16日
分类于 Geometry
需要 1 分钟阅读时间

平面直角坐标系的点绕原点旋转公式及证明

设点 $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）：

\[ \begin{aligned} x' & = r \cos (\alpha + \beta) \\ & = r(\cos \alpha \cos \beta - \sin \alpha \sin \beta) \\ & = r\cos \alpha \cos \beta - r\sin \alpha \sin \beta \\ & = x \cos \beta - y \sin \beta \\ \end{aligned} \]

\[ \begin{aligned} y' & = r \sin (\alpha + \beta) \\ & = r (\sin \alpha \cos \beta + \cos \alpha \sin \beta) \\ & = r \sin \alpha \cos \beta + r\cos \alpha \sin \beta \\ & = y \cos \beta + x \sin \beta\\ \end{aligned} \]

结论：点 $(x,y)$ 绕原点逆时针旋转 $\theta$ 后坐标为 $(x \cos \theta - y \sin \theta, x \sin \theta + y \cos \theta)$。

2024年6月16日
分类于 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} \]

2024年4月30日
分类于 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)$

逆变换

我们只需要对照正变换中的操作步骤，一步一步撤销变换即可

即对于 $i \in [0,2^{n-1})$，将 $\hat A_{i+2^{n-1}}$ 减去 $\hat A_{i}$ 的贡献，然后再递归地求解

当然还有另外的做法，即我们要将长度为 $2^n$ 的 $\hat A_i$ 在全集为 $2^n-1$ 的情况下（即不考虑目前的长度外的子集）只包括自己的 $A_i$，那么我们递归地求解完左右两个区间后，肯定有 $\forall i\in [0,2^{n-1}),\hat A_{i+2^{n-1}}=\hat A_i+A_{i+2^{n-1}}$，因此减去贡献即可

in brief，可以先递归再减贡献，这样逆变换与正变换只有一个 +/- 的变化

推广

对于 $\cap$ 的情况，与 $\cup$ 十分相似，请读者尽量自己构造变换，推一下式子，可以加深理解

如果没有思路，here

异或卷积

问题引入

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

原理

设 $\operatorname{popcnt}(i)$ 表示 $i$ 在二进制下 1 的个数，则有

\[ \operatorname{popcnt}(i \cap k) + \operatorname{popcnt}(j \cap k) \equiv \operatorname{popcnt}((i\oplus j)\cap k) \pmod 2 \]

证明：显然 $k$ 为 $0$ 的位上，$i,j$ 的取值不影响结果，那么设 $i'=i\cap k,j'=j\cap k$，那么问题转化为 $$ \operatorname{popcnt}(i') + \operatorname{popcnt}(j') \equiv \operatorname{popcnt}(i'\oplus j') \pmod 2 $$ 对于 $i',j'$ 每一位分开讨论，原命题易证

即异或不会改变 $1$ 的总数的奇偶性

正变换

我们尝试构造一个变换 $$ \hat A_i = \sum_j g(i,j) A_j $$ 例如对于 $\cup$ 卷积，$g(i,j)=[i\cup j=i]$

这个 $g$ 函数满足以下性质：

\[ \begin{aligned} & \because \hat C_i = \hat A_i \times \hat B_i \\ & \therefore \sum_{p} g(i,p)C_p = \sum_{j,k} g(i,j)\times g(i,k)\times A_j \times B_k \\ & \therefore \sum_{p} g(i,p) \sum_{j \oplus k = p} A_j \times B_k = \sum_{j,k} g(i,j)\times g(i,k)\times A_j \times B_k \\ & \therefore \sum_{j,k} g(i,j \oplus k) A_j \times B_k = \sum_{j,k} g(i,j)\times g(i,k)\times A_j \times B_k \end{aligned} \]

即我们要使得 $g(i,j)\times g(i,k) = g(i,j \oplus k)$

因为 $\operatorname{popcnt}(i \cap k) + \operatorname{popcnt}(j \cap k) \equiv \operatorname{popcnt}((i\oplus j)\cap k) \pmod 2$，我们发现 $g(i,j) = (-1)^{\operatorname{popcnt}(i \cap j)}$ 满足这个性质

\[ \hat A_i = \sum_j (-1)^{\operatorname{popcnt}(i \cap j)} A_j \]

手动推一下式子：

\[ \begin{aligned} \hat A_i \times \hat B_i & = \sum_j g(i,j)A_j \times \sum_k g(i,k) B_k\\ & = \sum_j (-1)^{\operatorname{popcnt}(i \cap j)} A_j \times \sum_k (-1)^{\operatorname{popcnt}(i \cap k)} B_k\\ & = \sum_{j,k} (-1)^{\operatorname{popcnt}(i \cap j) + \operatorname{popcnt}(i \cap k)} A_j \times B_k \\ & = \sum_{j,k} (-1)^{\operatorname{popcnt}(i \cap (j \oplus k))} C_{j \oplus k} \\ & = \sum_{p} (-1)^{\operatorname{popcnt}(i \cap p)} C_p \\ & = \sum_p g(i,p) C_p \\ & = \hat C_i \end{aligned} \]

快速变换

有点抽象，画个 $n=3$ 的图来模拟一下

快速变换图解

假设现在我们要考虑从 $n=2$ 到 $n=3$ 的变换，我们发现左边是 0??，右边是 1??，分别多出一个最高位

设原变换为 $F_i$ ，目标变换为 $G_i$

左 $\to$ 左

我们发现左边内部之间的 $\cap$ 结果不变，因此 $\forall i<4, G_i \gets F_i$

左 $\to$ 右 / 右 $\to$ 左

我们发现 0?? $\cap$ 1?? = 0??，因此其 1 的个数不变，因此 $\forall i<4,G_i \gets F_{i+4}, G_{i+4} \gets F_i$。

右 $\to$ 右

我们发现之前是 ?? $\cap$ ?? = ??，但是现在在前面加了一个 1，因此 $-1$ 的指数加一，所以 $\forall i<4,G_{i+4} \gets -F_{i+4}$

综上，我们有 $\forall i<4,G_i=F_i+F_{i+4}, G_{i+4}=F_i-F_{i+4}$

generally，对于从 $n-1$ 到 $n$ 的变换，我们有

\[ \forall i<2^{n-1}, G_i=F_i+F_{i+2^{n-1}}, G_{i+2^{n-1}}=F_i-F_{i+2^{n-1}} \]

时间复杂度 $O(n2^n)$。

逆变换

对照上面式子易得 ~~（留给读者思考）~~

模板题

核心代码如下

void fwtOr(ll *a,int n,int type) {
    for(int i=1; i<(1<<n); i<<=1)
        for(int j=0; j<(1<<n); j+=(i<<1))
            for(int k=0; k<i; ++k)
                (a[j+k+i]+=type*a[j+k])%=P;
}
void fwtAnd(ll *a,int n,int type) {
    for(int i=1; i<(1<<n); i<<=1)
        for(int j=0; j<(1<<n); j+=(i<<1))
            for(int k=0; k<i; ++k)
                (a[j+k]+=type*a[j+k+i])%=P;
}
void fwtXor(ll *a,int n,int type) {
    for(int i=1; i<(1<<n); i<<=1)
        for(int j=0; j<(1<<n); j+=(i<<1))
            for(int k=0; k<i; ++k) {
                ll u=a[j+k],v=a[j+k+i];
                a[j+k]=(u+v)%P;
                a[j+k+i]=(u-v)%P;
                if(type==-1) {
                    (a[j+k]*=Pi2)%=P;
                    (a[j+k+i]*=Pi2)%=P;
                }
            }
}

进阶理解

$\rm FWT$ 的变换本质实际上是构造 $g$ 的过程。

设 $\hat A_i = \sum_j g(i,j) A_j$，那么这个 $n \times n$ 的 $\lceil$转移矩阵$\rfloor$ 被称为位矩阵。

对于不同的卷积形式，我们需要构造不同的位矩阵。

特别注意由于我们需要逆变换，因此矩阵必须有逆。

形式化地，对于 $\odot$ 卷积，即 $C_i = \sum_{j \odot k = i} A_j B_k$，我们需要构造如下位矩阵：

\[ \begin{aligned} & \hat C_i = \hat A_i \hat B_i \\ \iff & \sum_j g(i,j) C_j = \sum_j g(i,j) A_j \sum_k g(i,k) B_k \\ \iff & \sum_j g(i,j) C_j = \sum_j \sum_k g(i,j) g(i,k) A_j B_k \\ \iff & g(i,j \odot k) = g(i,j) g(i,k) \end{aligned} \]

写的不是很严谨，请读者自己手推一下。

对于上文的三类卷积，其位矩阵的构造显然为

\[ g_{\cup}(i,j) = [i \cup j = i] \\ g_{\cap}(i,j) = [i \cap j = i] \\ g_{\oplus}(i,j) = (-1)^{\mathrm{popcnt} (i \cap j)} \]

$\rm FWT$ 的线性性

设 $\mathrm{FWT}(A)_i = \hat A_i = \sum_j g(i,j) A_j$，则有如下引理。

$\mathrm{FWT}(A+B) = \mathrm{FWT}(A) + \mathrm{FWT}(B)$

根据公式显然。

$\mathrm{FWT}(cA) = c\mathrm{FWT}(A)$

这个也是显然（

$\mathrm{FWT}(A^{-1})_i = g(i,0) \mathrm{FWT}(A)_i^{-1}$

\[ \begin{aligned} & \mathrm{FWT}(A^{-1})_i \mathrm{FWT}(A)_i \\ & = \sum_j g(i,j) A^{-1}_j \sum_k g(i,k) A_k \\ & = \sum_j \sum_k g(i,j \odot k) A^{-1}_j A_k \\ & = \sum_{p} g(i,p) \sum_{j \odot k = p} A^{-1}_j A_k \\ & = \sum_{p} g(i,p) [p=0] \\ & = g(i,0) \\ \end{aligned} \]

2024年4月24日
分类于 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}$

考虑快速计算

Zeta 变换

定义长度为 $2^n$ 的序列的 Zeta 变换 为

\[ \hat A_i = \sum_{j \subseteq i}{A_j} \]

即子集和

它具有一下性质：

\[ \hat B_i \times \hat C_i = \sum_{j \subseteq i} B_j \times \sum_{k \subseteq i} C_k = \sum_{p \subseteq i} \sum_{j \cap k = p} B_j \times C_k = \sum_{p \subseteq i} A_p = \hat A_i \]

相当于 FFT 中的点值表示法，用以加速卷积过程

快速变换

暴力求解 $\hat A$ 最优时间复杂度为 $3^n$，考虑加速

考虑 子集DP ，有一篇很好的博客¹，这里大概讲解一下。

其实 $\hat A$ 本质上是一个高维（$n$ 维）前缀和

如果我们要求二维前缀和，显然可以通过一下代码实现：

// 1st
for(int i=1; i<=n; ++i)
    for(int j=1; j<=m; ++j)
            a[i][j]+=a[i-1][j];
// 2nd
for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
            a[i][j]+=a[i][j-1];

我们发现 1st 完成后 a[i][j] 表示的是 $\sum_{k \le i} a_{k,j}$，即 $(i,j)$ 上方的元素和

那么 2nd 便是将 $(i,j)$ 左边操作后的 $\sum_{k \le j} a_{i,k}$ 累加到 a[i][j] 中，即完成二维前缀和

下面拓展到三维前缀和

// 1st
for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
        for(int k=1; k<=n; ++k)
            a[i][j][k]+=a[i-1][j][k];
// 2nd
for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
        for(int k=1; k<=n; ++k)
            a[i][j][k]+=a[i][j-1][k];
// 3rd
for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
        for(int k=1; k<=n; ++k)
            a[i][j][k]+=a[i][j][k-1];

类似地，1st,2nd 中处理除了第 k 平面中的二维前缀和，3rd 在立体空间中把他们加起来，成为三维前缀和

回到 Zeta 变换：

\[ \hat A_i = \sum_{j \subseteq i}{A_j} \]

如果我们用二进制 $(x_{n-1}x_{n-2}x_{n-3}\ ...\ x_2x_1x_0)_2$ 表示集合 $i$，二进制 $(y_{n-1}y_{n-2}y_{n-3}\ ...\ y_2y_1y_0)_2$ 表示集合 $j$

那么 $\hat A_i$ 可以被视为 $n$ 维前缀和，即 $$ \hat A_i = \sum_{y_{n-1}\le x_{n-1},y_{n-2}\le x_{n-2}, ..., y_1\le x_1,y_0\le x_0} A_j $$

当然，下标都为 0/1

因此，我们有如下 Code：

for(int i=0; i<n; ++i)
    for(int j=0; j<(1<<n); ++j)
        if(j&(1<<i))
            a[j]+=a[j^(1<<i)];

以上 Code 的 naive 形式为：

for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(i1>0) a[i1][i2][...][in]+=a[i1-1][i2][...][in];
for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(i2>0) a[i1][i2][...][in]+=a[i1][i2-2][...][in];
...
for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(in>0) a[i1][i2][...][in]+=a[i1][i2][...][in-1];

~~不要质疑我代码编译不通过~~

因此，我们用 $O(n2^n)$ 的时间复杂度解决了 Zeta 变换

逆变换

warning：此处不是 莫比乌斯反演！

众所周知，前缀和的逆运算即为差分

我们发现，只需要先将最后一维差分，即可将序列处理为 $n-1$ 维前缀和

即

for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(in>0) a[i1][i2][...][in]-=a[i1][i2][...][in-1];
...
for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(i2>0) a[i1][i2][...][in]-=a[i1][i2-2][...][in];
for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(i1>0) a[i1][i2][...][in]-=a[i1-1][i2][...][in];

但实际上因为前缀和都是无序的，因此我们直接正着做就可以啦

只需要把正变换的 += 改为 -= 就可以了

扩展

有时候，题目给的不是 $\cap$ ，而是 $\cup$ 怎么办？

那我们重定义 Zeta 变换 为： $$ \hat A_i = \sum_{i \supseteq j} A_j $$ 再推一下式子： $$ \hat B_i \times \hat C_i =\sum_{i\supseteq j} B_j \times \sum_{i\supseteq k} C_k =\sum_{i\supseteq j,i\supseteq k} B_j \times C_k =\sum_{i\supseteq p} \sum_{j \cup k=p} B_j \times C_k =\sum_{i\supseteq p} A_p =\hat A_i $$ 变换即超集和，高维后缀和

求法也很简单，只用将源代码中的 if(j&(1<<i)) 该为 if(!(j&(1<<i))) 即可

是 $\oplus$ 怎么办？

~~快去学 FWT 吧~~

例题

ABC349F

再送你一个并/交集的小口诀：下并或，上交与

高维前缀和总结(sosdp) - heyuhhh - 博客园 (cnblogs.com) ↩↩↩

2024年4月21日
分类于 Record
需要 2 分钟阅读时间

AtCoder 训练记录

~~先贴上本人主页~~

ABC347

$\Delta=\color{red}{-24}$

~~蓝名保卫战，极限 1600~~

C 题还是有些思维难度的，最后才做出来，但是不够简洁

E 题忘开 %lld 喜提罚时

D 题最难评，又 WA 又 RE，最后如果输出不符合条件就输出 -1 才过

F 题原题，但是不会（

赛后发现就是一个二维前缀和 + 二位前缀max，还是挺简单的

~~G 题不会~~

赛时打的太急了，罚时太多，速度也被拖慢了，同分的最高 performance 有 2000+，还是代码实现不够快和准

AGC066

$\Delta=\color{red}{-21}$

~~E 题原题，还抓了一个抄题解的~~

A 题还是挺水的，只是没想到从奇偶性的角度来想，题解给的是 $O(N ^ 2 D)$ 的做法，但是有更优且更简单的做法 $O(N ^ 2)$，但是没想到，还是考思维。

B 题有点愚人节，python 语言优势很大（自带高精度），用几个 $5 ^ x$ 拼起来多随机几次就完了，难绷（

~~蓝名没了 /ll~~

ABC348

$\Delta=\color{green}{114}$

performance 2300+ 祭

0罚时切 A ~ F，~~让我又想起了那场似的 rating~~

F 题听说比较水，暴力 + O3 可过，但是我用 bitset $O(\frac{N ^ 2 M}{\omega})$ 也过了（

G 题决策单调性优化板题，原题两道：here & here ~~（但我不会）~~

upd on 2024.4.14 : G 题改出来了，应用单调性还是比较简单的，但是难在证明

ABC349

$\Delta=\color{green}{67}$

A ~ D 都比较顺畅，D 题盲猜 $\text{lowbit}$ 喜提机房一血，E 题没开 long long 喜提一发罚时与机房一血

然后就坐着与 F & G 干瞪眼，F 先是用 cdq 尝试水分，后来将不是 $M$ 因数的删掉了，还是不行

最后发现 $M$ 最多有 $13$ 个因数，直接 $O(2^{13}N) \approx 1.638 \times 10^9$ 过了，~~AtCoder 神机~~

但是打得太急，F 题 7 发罚时，最后 4 发最离谱，一发没取模，一发取模太慢 TLE，一发将取模改成减法写错了，最后一发两处取模是 copy 的都错了，漏了一处没改（

$\color{green}{525} \color{red}{(7)}$ ！！

G 题直接并查集开水，快 T 了就 No，过了一半的数据点

实际上还可以开随机化，因为对于 $\forall i$，有些连边是不需要的，有概率连到与目标解答案相同的状态，但比赛后才想到（

ABC350

$\Delta=\color{red}{-6}$

之前的总结写的太笼统了，更像是提要。刚好今天实在是打 emo 了，犯了很多离谱的错误，想写一篇个人直观的反思，从 rating 和 performance 中跳出来，慢慢地审视整个过程。

A 题其实没有问题，可以直接A的，但是把 %03d 写成了 %02d 样例中也没有 ABC001，于是就挂了。

后来几道题一直很慌，越慌，越是想打快。越是快，就越出错。这很严重拖慢了整个切题的速度。C 题本来是没什么问题的，但是急着想过掉它，核心的代码几乎一半是错的，第一发直接罚时，这时心情也是很差了，很焦躁。后来逼迫自己冷静下来，又在草稿纸上画了几下，思路便逐渐清晰，于是便改对了。

到了赛点的后三题后，我其实刚刚松一口气，看到 E 题又自闭了，毕竟概率题上次就栽过，是ABC342F，这次又看到，心里一紧，只好先尝试 F 题。

F 题读完题后没多久就想到了 dfs，然而实现中还是有一些小错误，如 for 循环里更新 i 的话，它实际上还会 ++i/--i 一次，会跳过一个位置。好在没罚时。

切完 F 题后看了一下 G 题，一开始读错题了以为那个在线是假的，高高兴兴拿样例试水发现是错的。没办法，于是看 E 题，结果旁边的人 ~~看我蓝名快没了~~ 好心旁敲侧击，于是想到 DP，中途还有一个自己转移到自己的，想到了之前的一道题目 ~~虽然我没改出来~~ ，于是移项解方程即可。

一开始 $10^{18}$ 我认为计搜是过不了的，因此打得不够坚定，还有一个变量重名调了很久，实现不够稳和准。开始是想着拿去水分的，但是直接过了，而且时间也很充裕（7ms）。赛后看题解，计搜时间复杂度实际上是 $O(\log^3 n)$，但是主要问题是不会证明，对自己没有信心，于是犹豫了很久。

到了最后的 G 题，此时还剩下 20 分钟，已经机房内有人切了 G 题。出于对 G 题的潜意识压力以及前面比赛的表现，我此时已经基本失去思考能力了，脑子一片嗡嗡的根本想不到正解，打了一个根本就没概率的随机化过了一半，最后遗憾收场。

机房内同年级的有 4 个人过了 G 题，其中 3 人都是水过的，还包括两个代码相似的人。第四个大佬用了 splay。

到这里，你可能认为 G 题还是有点难度的。但是，实际上，这也是我在比赛中犯的最后一个，也是最大的一个错误。

读完 G 题，其实不难想到如果维护好了森林中的每棵树有确定的根（具体是哪个节点与答案无关），并且维护好了每个点在其所在连通块中的朝向这个根的父亲，那么求解答案是 $O(1)$ 的。比赛时这个念头在我脑海里一闪而过，但是很快就被否决了——原因很简单，这个维护过程直观上看是非常不可行的。后来，我转而去想 bitset 时间换空间，但一无所获。

然而，这就是问题所在——用暴力维护这些信息实际上的时间复杂度是正确的！因为每次连边的两个点都是在不同的连通块中，做完这次操作以后它们就会被合并，因此如果我们遍历一遍较小的连通块，总时间复杂度是 $O(n\log n)$！因此，这道 G 题出乎意料地短，甚至比我的随机化代码还要少。

写在最后：这次 ABC 可以看到除了少部分人，大多数人都没有取得很理想，甚至可以说糟糕的成绩。比赛结束后，我听到有人在机房里咒骂自己、题目和出题人的。还有人为了 rating 而闷闷不乐，诸如此类。但是有一点他们都错了，我们打比赛不是为了 rating 去打，不是为了成绩去打。以我为例，这次比赛我的 delta 是 -6，相对于之前 2200+ 的 performance，可谓是相当的差。但是，在这背后，是我被打乱的做题节奏，被扰乱的心态，是我过于激动的心情。这次比赛，暴露了我很多问题：代码实现不准不细心，读题不仔细，对时间复杂度的不敏感，对时间复杂度证明的不熟练，而这些，都为我提供了宝贵的经验，这远远不是几点 rating 所能给我的。之前还看到旁边的人比赛时一起讨论题目，其实也是十分不应该——如果人人都只在乎 rating 以至于无人在乎算法背后的玄妙，在乎它们的出处与归宿，那么 rating 早已失去它本来的意义了。希望各位在天涯海角的 OIer 都能保住自己的初心，守住心中的一寸净土，为了 OI，ACM，乃至 CS 的明天而砥砺前行。

2024

平面直角坐标系的点绕原点旋转公式及证明

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

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

与/或卷积

问题引入

正变换

快速变换

逆变换

推广

异或卷积

问题引入

原理

正变换

快速变换

逆变换

模板题

进阶理解

\(\rm FWT\) 的线性性

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

定义

Zeta 变换

快速变换

逆变换

扩展

例题

AtCoder 训练记录

ABC347

AGC066

ABC348

ABC349

ABC350