筛素数的算法

朴素筛法

朴素的筛素数算法的流程是这样的：

1. $i$ 没有被标记，$i$ 是素数；用 $i$ 去标记所有的 $i,2i,\cdots,\left\lfloor \frac{N}{i} \right\rfloor \times i$
2. $i$ 被标记，$i$ 不是素数

*** 离线文档***

扩展欧几里得算法

问题描述

已知 $a,b$ 为常整数，求方程 $ax+by=\gcd(a,b)$ 的一对整数解?

问题简析

令 $\displaystyle
\left\lbrace\begin{aligned}
&A=a(\hskip -1em \mod b) \
&B=b
\end{aligned}\right.
$，构造方程 $$AX+BY=\gcd(A,B). \hskip 5em (1)$$

*** 题目链接 ***
*** Code ***

题意简述

一个长度为 $L$ 的串 $a_0a_1\cdots a_{r-1} * a_{r+1}a_{r+2}\cdots a_{L-1}$ 表示算式：$A \times B$。其中：

$$
\begin{aligned}
&A = \sum_{i=0}^{r-1} \left( a_i \times 10^{r-i-1} \right) \
&B = \sum_{i=r+1}^{L-1} \left( a_i \times 10^{L-i-1} \right) \
\end{aligned} \
0\leqslant r < L, \hskip .5em 0\leqslant a_i\leqslant 9, \hskip .5em 0\leqslant i < L \text{且} i \neq r \
$$

算法简介

树链剖分是将树上的节点映射到一段连续的区间中，使得树上任意一条路径能用不
超过 $O(\log N)~$ 段连续区间表示。这样就可以对树上的路径做一些操作了。
常见的搭配是 线段树+树链剖分。

*** 题目链接 ***
*** Code ***

题意简述

一棵 $N$ 个节点的树，以 1 为根。树上的每个节点有两个权值：$v_i$，$t_i$。初始时均为 0。
$Q$ 次操作：

• 1 u d $\hskip .6em$ 对 $u$ 到根上所有点的 $v_i \text{+=} d$
• 2 u d $\hskip .6em$ 对 $u$ 到根上所有点的 $t_i \text{+=} v_i \times d$

输出 $Q$ 次操作后所有节点的权值。

数据范围：$N,Q \leqslant 10^5$。
数据保证 64 位整数不会溢出。

准备

组合数

$$
\binom{n}{m} = C(n,m) =
\left\lbrace \begin{aligned}
&\frac{n!}{m!~(n-m)!}, &n \geqslant m \
&0, &n < m
\end{aligned} \right.
$$

算法简介

Manacher 算法能够在线性时间内求出一个字符串的最长回文子串。

算法原理

记原字符串为 S，长度为 N。
在 S 中的任一对相邻字符间插入一个特殊字符**’$’**，目的是保证新串中所有的回文子串长度都为奇数。
设以 s[i] 为中心的最长回文串长度为 $2R[i]+1$。
那么，如果 $j < i$ 且 $j+R[j] > i$；作 $i$ 点关于 $j$ 的对称点 $i’$，则必有 $i’ > j-R[j]$。

*** 题目链接 ***
*** Code ***

题意简述

在一个 $N\times M$ 的矩形方格地图中，有一条长度为 $L$ 的贪吃蛇。
地图的 (1,1) 位置是一个出口，如果贪吃蛇能移动到出口，输出最短步数（头到达出口的步数）；否则输出 -1。
贪吃蛇的移动规则：

• 只能朝边相邻的格子移动
• 不能朝障碍物移动（身体及四周墙壁都视作障碍物）

数据范围： $1\leqslant N, M\leqslant 8$，$2\leqslant L\leqslant 8$。

*** 题目链接 ***
*** Code ***

题意简述

一棵 $N$ 个节点的树，节点编号 $1 \sim N$，且根节点编号始终为 1。
初始时，节点 $i$ 的颜色为 $c_i$。
$M$ 次操作：

• 0 u c $\hskip .6em$ 将以 u 为根节点的子树中所有的节点颜色染成 c
• 1 u $\hskip 1.5em$ 输出 u 为根节点的子树中颜色种数

数据范围： $1\leqslant T\leqslant 100$，$1\leqslant N, M\leqslant 10^5$, $1\leqslant c_i\leqslant N$。

*** SomethingAboutFFT.pdf ***

小记

说起来，实在要感谢 lyl 学长（可能他并不想我写上他的名字，以下以他常用的名字 SparklingWind 指代）。
大一的时候看了 SparklingWind 的《高中生学 FFT 算法》，当时自己实在太弱（虽然现在还是弱。。）
以至于看得云里雾里。后来 SparklingWind 教我用 LaTeX，实在是让我受益匪浅。
LaTeX 是一款精致的排版系统，可以漂亮、准确的表达出你心中所想。
于是，我决定要基于自己的理解用 LaTeX 写一份 FFT 的学习笔记云云的东西，我把它命令为 SomethingAboutFFT，
初衷是担心 LaTeX 这种软件对中文名不友好。。。