Math

最近刚完成某 N 厂的 OA 题目，难度比想象中高了很多，不过里面的问题非常有意思。正好趁求职这段时间复盘一下题目，顺带挖掘一下隐含的一些问题。

要求：给定 $n, m, k$，其中 $n, m, k$ 都是正整数，模拟重排过程并返回调用moveRobot的次数，越少越好。SPJ 会检查重排后的结果。

没事瞎水博客系列……

为了深入理解这个操作背后的原理，我参考了 StackExchange 上的这篇回答。从他的证明过程中我发现了一个关键：排序前后两个矩阵的关系可以用排列/置换（permutation）来刻画。下面我将站在线性代数的视角来系统化解释一下“名次向量”背后的原理。

龟速补上欠下的账 ing……

写完发现读着好晦涩，但数学不就是这样的吗🌚

$G = (V, E)$ 是有向、无平行边的图，每条边边权为正，其中有一个源点（source）$s$ 和汇点（sink）$t$ 满足：没有一条边以 $t$ 为起点，或以 $s$ 为终点。

对某边 $e \in E$，记该边边权为 $c(e)$。

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

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

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

一个整数 $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!$ 个。