加边,删边,询问之中怎料变幻无常;
左旋,右旋,伸展背后暗含均摊平衡。
Pause and ponder
受这几天看到的不少高维前缀和题目的影响,我决定系统地学习一下集合幂级数的一套理论了。内容主要来自2015年吕凯风(VFleaKing)国家集训队论文《集合幂级数的性质与应用及其快速算法》(pdf版本会放在附录里),包括集合并卷积、集合对称差卷积、子集卷积、快速莫比乌斯变换、快速莫比乌斯反演、快速沃尔什变换及逆变换等,以及附带进行的一些练习。
(UPD 2021.4.20) 推荐观看:Fourier Analysis of Boolean functions || @ CMU || Lecture 8a of CS Theory Toolkit
一个长度为 $1$ 的线段上随机撒 $n-1$ 个点,形成了 $n$ 条线段,那么这 $n$ 条线段中第 $k$ 短($k\leq n$)的线段期望长度是多少呢?答案是:
$$
\frac 1n \sum_{i=0}^{k-1} \frac 1{n-i}
$$
例如, $n$ 条线段中最短的线段期望长度是 $\frac 1 {n^2}$,第二短的期望是 $\frac 1n (\frac 1n + \frac 1{n-1})$ ,依此类推。
事实上,这 $n$ 条线段期望的长度分布是指数分布,可以类比玻尔兹曼分布,少数较长的线段占据了大部分长度。而如果按照从左往右的顺序的话,每条线段长度都服从相同的概率分布,概率密度函数都是 $\displaystyle f(x) = (n-1) \cdot (1-x)^{n-2}$ 。
最近我一直在刷潘承洞、潘承彪的《初等数论》,感觉还是学到了不少东西呢。从现在我就来做一个数论之旅系列专题笔记吧,顺便也记录一下我的学习历程。
这一次笔记对应的是《初等数论》第四章同余方程 4.5 到 4.9 的内容,主要介绍二次剩余理论,包括欧拉判别法,勒让德符号,二次互反律,雅克比符号等,以及高次同余方程简介,给出了 $n$ 次剩余的判别公式。
在开始之前约定一下我的记号吧。未经说明的任何字母都代表自然数,小写字母 $p$ 始终代表奇素数,而大写的 $P$ 则不一定。