题目链接：LOJ 2000
Doris 刚刚学习了 $\text{Fibnacci}$ 数列，用 $f[i]$ 表示数列的第 $i$ 项，那么：
$$ \begin{align*} f[0] &= 0 \\ f[1] &= 1 \\ f[n] &= f[n - 1] + f[n - 2], n \ge 2 \end{align*} $$
Doris 用老师的超级计算机生成了一个 $n \times m$ 的表格，第 $ i $ 行第 $ j $ 列的格子中的数是 $f[\gcd(i, j)]$，其中 $\gcd(i, j)$ 表示 $i$ 与 $j$ 的最大公约数。
Doris 的表格中共有 $ n \times m $ 个数，她想知道这些数的乘积是多少。
这些数的乘积实在是太大了，所以 Doris 只想知道乘积对 $10 ^ 9 + 7$ 取模后的结果。
本题有 $T$ 组数组。
数据范围：$1 \le T \le 1000$，$1 \le n, m \le 10 ^ 6$。
题目链接：UOJ 395
小 A 被选为了 ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。
由于 ION 已经举办了很多届，所以在题目命名上也是有规定的，ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。
由于一些特殊的原因，小 A 不知道 ION2017 每道题的名字，但是他通过一些特殊手段得到了 ION2017 的命名串，现在小 A 有 $Q$ 次询问：每次给定 ION2017 的命名串 $S$ 和 ION2018 的命名串 $T$，求有几种题目的命名，使得这个名字一定满足命题委员会的规定，即是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。
由于一些特殊原因，所有询问给出的 ION2017 的命名串都是某个串的连续子串 $S[l \dots r]$。
数据范围：$1 \le \lvert S \rvert \le 5 \times 10 ^ 5$，$1 \le Q \le 10 ^ 5$，$\sum \lvert T \rvert \le 10 ^ 6$，$1 \le l \le r \le \lvert S \rvert$。
题目链接：Codeforces 432D
你有一个字符串 $S$，你需要求出所有匹配的前后缀，并计算出这些前后缀在字符串中出现的次数。
数据范围：$1 \le \lvert S \rvert \le 10 ^ 5$。
题目链接：Codeforces 633C
Yash 研究出了一种新的密码技术。对于给定的句子，密码通过以下方法生成：
现在 Yash 给你一个长度为 $n$ 的加密后的句子 $S$ 和一个长度为 $m$ 的单词列表 $w_i$。请你帮助他找出任何一种可能的原始句子，使得句子里的单词都来自于单词列表。注意：任何给定的单词都可以多次使用。
数据范围：$1 \le \lvert S \rvert \le 10 ^ 4$，$1 \le m \le 10 ^ 5$，$1 \le \lvert w_i \rvert \le 10 ^ 3$，$\sum \lvert w_i \rvert \le 10 ^ 6$。
题目链接：Codeforces 1028C
在平面中给你 $n$ 个矩形，我们用左上角 $(x_1, y_1)$ 和右下角 $(x_2, y_2)$ 坐标描述一个矩形，保证其中存在 $n - 1$ 个矩形使得他们有公共点。如果一个点严格属于矩形内部或在它的边界上，那么认为这个点属于这个矩形。你需要找到一个整数坐标，使得它属于至少 $n - 1$ 个矩形。
数据范围：$2 \le n \le 132674$，$-10 ^ 9 \le x_1 < x_2 \le 10 ^ 9$，$-10 ^ 9 \le y_1 < y_2 \le 10 ^ 9$。
题目链接：LOJ 2033
魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 $1$、$2$ 拼凑起来形成一个魔咒串 $[1, 2]$。
一个魔咒串 $S$ 的非空子串被称为魔咒串 $S$ 的生成魔咒。
例如 $S = [1, 2, 1]$ 时，它的生成魔咒有 $[1]$、$[2]$、$[1, 2]$、$[2, 1]$、$[1, 2, 1]$ 五种。$S = [1, 1, 1]$ 时，它的生成魔咒有 $[1]$、$[1, 1]$、$[1, 1, 1]$ 三种。
最初 $S$ 为空串。共进行 $n$ 次操作，每次操作是在 $S$ 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 $S$ 共有多少种生成魔咒。
数据范围：$1 \le n \le 10 ^ 5$，$1 \le \Sigma \le 10 ^ 9$。
题目链接：Codeforces 700E
Bomboslav 成立了一个品牌代理商，正在帮助公司创建商标和广告。就这个问题而言，公司的广告应该是其名称的非空子串。
有时，公司会对品牌进行重塑并改变广告。如果广告 $B$ 作为子串在广告 $A$ 中出现至少 $2$ 次（允许重叠），那么认为广告 $A$ 比 $B$ 更酷。
你得到了某个公司的名字 $w$，你的任务是帮助 Bomboslav 确定最长的广告序列 $s_1, s_2, \dots, s_k$ 满足任何一个广告都比上一个更酷。
数据范围：$1 \le \lvert w \rvert \le 2 \times 10 ^ 5$。
题目链接：Codeforces 1150D
在中东考古研究期间，你发现了三种古代宗教的遗迹：第一宗教、第二宗教和第三宗教。你收集到了每一种宗教的演变信息，你现在想知道三种宗教是否可以和平共处。
宇宙之词是一个长度为 $n$ 的只包含小写字母的单词。在任何时候，每一种宗教都可以用一个由小写字母组成的单词来描述。
如果描述这三种宗教的单词是宇宙之词的不相交子序列，那么他们的信徒就可以和平共处。形式化地，我们能够对宇宙之词的若干位置给定一个标号 $1, 2, 3$，那么标号为 $i$ 的位置构成的单词就是第 $i$ 种宗教的描述。
然而，宗教是在不断发展的。最初，每个宗教的描述都是空的；在发展过程中，宗教进行了 $q$ 次变化。每次变化中，要么将一个字符附加到某个宗教的描述的末尾，要么从某个宗教的描述的末尾删除一个字符。每次变化后，你都需要判断宗教是否可以和平共处。
数据范围：$1 \le n \le 10 ^ 5$，$1 \le q \le 1000$，$\lvert \text{宗教的描述} \rvert \le 250$。
题目链接：Codeforces 1152D
Neko 把所有长度为 $2n$ 的合法括号序列插入到一棵 $\text{Trie}$ 树中，接着 Aki 向他提出了一个有趣的问题：在这个 $\text{Trie}$ 树中的最大匹配（找到最大的一组边，使得没有两条边具有公共顶点）的大小是多少？答案对 $10 ^ 9 + 7$ 取模。
数据范围：$1 \le n \le 1000$。
题目链接：Codeforces 1152C
Neko 有两个整数 $a$ 和 $b$，他的目标是找到一个非负整数 $k$ 使得 $\operatorname{lcm}(a + k, b + k)$ 尽可能小。如果有 $k$ 有多组解，他会选择最小的一个。
数据范围：$1 \le a, b \le 10 ^ 9$。