数论中的一个小概念，也是 NTT 的基础。 阶 若 $\gcd(a,m) = 1$，使 $a^l \equiv 1 \pmod m$ 成立的最小正整数 $l$，称为 $a$ 关于模 $m$ 的阶，记为 $\text{ord}_m a$。 若 $\text{ord}_m a = l$，则 $\t...

CF704E Iron Man 题意 给定一棵 $n$ 个点的树。 有 $m$ 个人，第 $i$ 个人会在 $t_i$ 时刻出现在 $v_i$，并以每时刻 $c_i$ 条边的速度向 $u_i$ 移动，到达 $u_i$ 立刻消失。出现的时段是左闭右闭的，因此...

CF671E Organizing a Race 题意 有 $n$ 个点排成一行，第 $i$ 个点与第 $i + 1$ 个点之间的距离为 $w_i$ 个单位。 每个点都有一个加油站，第 $i$ 个点的加油站可以给你的车加能跑 $g_i$ 个单位的油。 若一...

CF666E Forensic Examination 题意 给定一个字符串 $s$，以及 $m$ 个字符串 $t_{1 \dots m}$。 $q$ 次询问，每次询问 $s[p_l:p_r]$ 在字符串 $t_{l\dots r}$ 中的哪个串里作为子串出现的次数最多，如果有...

CF700E Cool Slogans 题意 给定一个长度为 $n$ 的字符串 $s$。 你要构造一个最长的字符串序列 $t_{1\dots k}$，满足： 对于 $i \in [1,k]$，$t_i$ 为 $s$ 的子串。 对于 $i \in [2,k]$，$t_i$ 在 $t_{i-...

因为 SA 就很有用了，所以一直不想学 SAM。突然不知道为什么就想学了，可能是为了吊打兔兔吧。 后缀自动机 (SAM) 是一个能解决许多字符串相关问题的有力的数据结构。 直观上，SAM 可以理解为将字符串的所...

CF643D Bearish Fanpages 题意 给定一个 $n$ 个点的基环森林，第 $i$ 个点与 $f_i$ 之间有一条边。 保证在任意时刻，这个基环森林中的环长至少为 $3$。 当一种「神秘事件」发生时，对于第 $i$ 个点，设与...

CF666D Chain Reaction 题意 平面直角坐标系中有四个整点。 你可以将每个点水平或者垂直移动到一个整点，使得这四个点恰好成为一个平行于坐标轴的正方形的顶点（正方形不能退化成一个点）。 如果存在移动...

CF708E Student's Camp 题意 有一个 $(n+2) \times m$ 的网格。 除了第一行和最后一行，其他每一行每一天最左边和最右边的格子都有 $p$ 的概率消失。 求 $k$ 天后，网格始终保持连通的概率。 $n,m \le 1.5...

CF696F ...Dary! 题意 给定一个 $n$ 个点的严格凸多边形。 你要最小化 $r$，使得可以在这个多边形内或多边形上找到两个点，以它们为圆心以 $r$ 为半径作两个圆，满足多边形的每条边所在的直线与至少一个圆...