Problem A Two Regular Polygons
(T) 次询问，给定 (n, m) ，问能否在正 (n) 边形的顶点上选 (m) 个点，使得这 (m) 个点构成的图形的中心与正 (n) 边形相同
- (Tleq10^4)
- (3leq m<nleq100)
满足 (m|n) 即可
Problem B Bogosort
(T) 次询问，每次给定一个长为 (n) 的序列 (a) ，问能否找到 (a) 的一种排列 (b) 使得 (forall i<j, j-a_j eq i-a_i)
- (Tleq100)
- (n, a_ileq100)
降序排序即可
Problem C Adding Powers
(T) 次询问，每次给定一个长为 (n) 的序列 (a) ，你有一个初始全为 (0) 的长 (n) 的序列 (b) ，在第 (i) 个时刻（从 (0) 开始），能选择一个 (pos) 并将 (b_{pos}+k^i) ，或者什么都不做，问能否将 (b) 变成 (a)
- (Tleq1000)
- (nleq30; kleq100; a_iin[0, 10^{16}])
判断给出的 (n) 个数中每个 (k_i) 是否出现了恰好 (0) 或 (1) 次
Problem D Count the Arrays
统计满足下列条件的长度为 (n) 的序列 (a) 个数：
- (forall 1leq ileq n, exist 1leq a_ileq m)
- (a) 中存在且仅存在一对相同元素
- 存在一个位置 (p) ，使得 (a_1, a_2, cdots, a_p) 严格单调递增， (a_p, a_{p+1}, cdots, a_n) 严格单调递减
答案对 (998244353) 取模
(nleq mleq2 imes10^5)
首先从 (m) 个数中选 (n-1) 个，除去最大数，剩下 (n-2) 个都能成为重复的数，除去最大数和两个重复的数，剩下 (n-3) 个可以自由选择是在最大数左侧还是右侧，因此答案为 (displaystyleinom{m}{n-1} imes(n-2) imes2^{n-3})
Problem E Array Shrinking
给定一个长为 (n) 的序列 (a) ，你可以任意进行以下操作：
- 找到一个 (i) 满足 (a_i=a_{i+1}) ，将两数删掉，替换成 (a_i+1)
问经过若干次操作后，序列长度最短是多少
(nleq500; a_ileq1000)
记 (dp_i) 为前 (i) 个数若干次操作后的最短长度，转移为 (dp_i=minig{dp_j+1 | 0leq j<i,) 区间 ([j+1, i]) 能合并成一段 (ig})
判定区间 ([l, r]) 能否合并成一段可以区间 dp，然后就做完了
Problem F Attack on Red Kingdom
咕了，留坑待填
Problem G Autocompletion
给定 (k) 个两两不同的串组成的集合 (S) ， (k) 个串构成的 trie 的节点数为 (n) ，对于每个给出串，求出将空串变成该串的最小化费。
设当前串为 (s) ，可以进行两种操作：
- 在 (s) 的最后添加任意一个字符，花费为 (1)
- 将所有 (tin S) 且 (s) 是 (t) 的前缀的 (t) 拿出来按字典序排序，对于排序后的第 (x) 个串 (t_x) ，可以花费 (x) 将 (s) 变成 (t_x)
(n, kleq10^6)
考虑把对串的操作看成边，操作 (1) 相当于从 trie 上的父亲向儿子连一条边权为 (1) 的边，操作 (2) 相当于将当前串 trie 上对应点 (u) 向它子树中所有属于集合 (S) 的串按字典序排序后连边权为 (1, 2, 3, cdots) 的边，接着跑最短路
操作 (2) 可以用线段树优化建图，给 (S) 中的所有串按字典序建成一个线段树，对于线段树上每个节点，向左儿子连边权为 (0) 的边，向右儿子连边权为 左儿子对应的区间大小 的边
时间复杂度 (O(nlog^2n)) ，CF上时限 7s，能跑过（）
考虑操作 (2) 给当前串 trie 上对应点 (u) 的子树造成了什么贡献，记 (rk_i) 为第 (i) 个串在 (S) 中字典序的排名，走到当前串的最小化费为 (x) ，则 (u) 的子树中所有属于 (S) 的串 (v) 的答案可以对 (x+rk_v-rk_u) 取 (min) （需特殊考虑 (uin S) 的情况），注意到 (rk_v) 对 (v) 而言是固定的，因此拿棵线段树维护区间 (x-rk_u) 的 (min) 即可，时间复杂度 (O(nlog n))