Posts

本文仅面向学习 FFT 算法的 CS 学生。文中关于傅里叶变换的阐述仅用于帮助快速简要地理解算法背后时域/频域变换的意义，逻辑性不会像「信号与系统」课那么强。本人没系统学过「信号与系统」这门课，能写出这篇文章也要感谢来自 FDU、SCUT 的两位同学的帮助。欢迎各位大佬对本文内容进行指正！

要系统学习「信号与系统」的内容，可参阅奥本海默著的《信号与系统》一书。

在我学习 FFT 时，第一个面对的问题背景是「给定两个多项式，如何快速求得二者的乘积？」老师或…

题目来自 Algorithm design / Jon Kleinberg, Eva Tardos.—1st ed. 的 4.3 节。

假设现在有一个容量为 $k$ 的缓存（cache）空间，和 $m$ 个内存 block 访问请求 $d_1, d_2, \dots, d_m$。对于第 $i$ 个请求 $d_i$，如果请求的 block 在缓存中，称其为一次命中（hit），否则称其为一次失效/缺页（miss）。若出现 miss，则需要从内存中读取该 block 并写入缓存（若缓存已满则会替换掉其中一个 block）。现给定请求序列，求一个最优缓存（caching）策略使得 miss 尽可能少。

想不到促使我学习插头 DP 的动机竟然是一道算法课的 Lab 题，还被网上的假教程演了半天……姑且把学到的东西写一写，纪念一下我对着一屏幕的表画了大半天图的自闭时光。

起这个标题的原因实在一篇博客里看到“转移过程十分码农”，敲完代码深以为然，就借用过来了。

以下内容仅为插头 DP 的一种应用情形。若要应用于其他题目，需要对过程略作修改。

前置知识：状态压缩 DP、BFS、哈希

一个整数 $x$ 对另一个整数 $p$ 的二次剩余，指 $x^2$ 模 $p$ 的余数。

我们称整数 $d$ 为模 $p$ 的二次剩余当且仅当 $\exists x \in \mathbb{Z} \text{ s.t. } x^2 \equiv d \pmod p$；反之，称 $d$ 为模 $p$ 的非二次剩余。

上下文无歧义的情况下可以简称为剩余和非剩余。

置换即 $[\![1, n]\!] \triangleq \{1, 2, \dots, n\}$ 到自身的 1-1 变换：$[\![1, n]\!] \rightarrow [\![1, n]\!]$

$p: i \rightarrow a_i, (a_i \neq a_j, i \neq j)$，

其中 $a_1, a_2, \dots, a_n$ 是 $[\![1, n]\!]$ 的一个全排列，

$n$ 阶置换共有 $n!$ 个。