多项式 / 算法 再探 FFT – DIT 与 DIF，另种推导和优化 本文将简单推导两种方式进行的离散傅里叶变换，用另种视角解释并优化算法。参考了 Seniorious yhx-12243 的 NTT 到底写了些什么（详细揭秘） 一文、OI Wiki 快速傅里叶变换 条... More 2023年2月23日 4
组合数学 / 题解 洛谷题库 P6031 Cards 加强版 – 题解与思路重现 洛谷题库 P6031 Cards 加强版 对于每一轮对局的 $m!$ 种排列，对于编号为 $a$ 的牌，恒有 $(m-1)!$ 种是以牌 $a$ 为首的。因此一轮可以归为 $m$ 种情况，首张为王牌的... More 2023年1月31日
OI MOCK NOIP 20220920 B – 骰子 另解题解 形式化题意 给定 $A+B$ 个本质相同的随机变量，在 $\{1,2,\cdots,6\}$ 内等概率取值。若两个随机变量 $a \in A, b \in B, a=b$，则二者相消为 $0$。求在所... More 2022年9月22日
OI 任意模数下快速数论变换的两种实现 我们实现NTT时，总是在 整数模质数 $p=2^kq+1$ 域上进行的。原因很简单：为了在 $\mathbb{Z}/p\mathbb{Z}$ 上使用原根以套用复数域 $\mathbb{C}$ 上“单位... More 2022年7月3日 1
OI FFT“三次转两次”优化 众所周知，由于做快速傅里叶变换时，要先将两个多项式 $f(x),g(x)$ 分别DFT，点值相乘后再IDFT，其常数是巨大的。但如果其系数均为实数，我们就可以通过构造多项式的方式，充分利用复数虚部存储... More 2022年7月3日 1
OI 分治FFT与循环卷积 洛谷题库 P4721【模板】分治FFT 给定数列 $g_{1\cdots n}$，求解满足如下形式的数列 $f$：$f_0=1,f_i=\sum_{j=0}^{i-1}f_jg_{i-j},\fora... More 2022年7月3日 2
