| rank | solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 10 | 11 | O | O | O | Ø | O | . | . | O | O | O | O | O | O |
A
Solved by Henry.
B
Solved by XLor.
打表乱搞。
从两边每次暴力取一个小的变化量生成 Treap，加亿点剪枝即可卡过。
C
Solved by Henry.
答案一定等于 $4x-1$ ($x$ 为 $X$ 的个数)。
将边分为两类，生成一个欧拉回路即可。
D
UpSolved by XLor.
求长度小于等于 $n$，字符集大小为 $k$ 的串中，有多少个存在弱双回文划分。
去重前的总方案数 $R(n)=\sum_{i=0}^{n-1} k^{\lceil \frac{i}{2} \rceil} k^{\lceil \frac{n-i}{2} \rceil }$。
但是，存在一些串有多种弱双回文划分，例如 $abaaba$ 有两种划分方式。有一个结论，这样的串一定是整周期串，且最小周期是 $p$，方案数为 $|s|/p$。
考虑 $D(n)$ 表示只有一种划分方式的本源串，则 $D(n)=R(n)-\sum_{l|n \land l<n} \frac{n}{l} D(l) $。
最终答案，考虑周期串后为 $\sum_{i=1}^n \sum_{l|i} D(l)$。
E
Solved by XLor.
$m$ 个关键点一起 $bfs$，每个点维护一下最短距离和多少个关键点能够以最短距离到达该点，转移时分从未访问过和最短距离相同，若出现一个点次数为关键点个数，即为答案。
H
Solved by Forsaken.
分块。
I
Solved by Henry.
J
Solved by Forsaken.
K
Solved by Forsaken.
L
Solved by XLor.
答案大于等于 $2$，扣一哈 $Runs$。
答案小于 $2$，$sam$ 上启发式合并一下。
M
Solved by XLor.
暴力枚举两个，std::map 维护另外一个。