Contest Info

practice link

Solutions

A. Grid game

签到题。

B. Game with modulo

签到题。

C. Johnny Solving

题目大意：给你一个 \(n\) 个点的连通图，每个点的度至少为 \(3\)，另外给你一个 \(k\)，要求你完成下面两个问题之一：或者找到一条长度至少为 \(\lceil\frac{n}{k}\rceil\) 的简单路径，或者找到 \(k\) 个简单环，每个环满足：

• 长度至少为 \(4\)
• 长度不是 \(3\) 的倍数
• 至少有 \(1\) 个点不在任何一个其它的环中

题解：首先我们找出该图的任意一棵生成树，如果该树的深度大于等于 \(\lceil\frac{n}{k}\rceil\)，那么我们就可以找到一条简单路径；否则这棵树至少有 \(k\) 个叶子，因为每一层的结点数不会超过叶子的数量。我们从每个叶子向上找简单环，由于每个叶子都至少有三条边，那么这 \({3\choose2}\) 个环里显然至少有一个长度不是 \(3\) 的倍数的环。

D. Professional layer

题目大意：有 \(n\) 个数 \(a_{i}\)，每个数有一个权 \(e_{i}\)。现在要求你将其中的一些数进行操作，每个数至多被操作一次。操作时将该数除以自己的某个约数，且该约数必须 \(\le k\)。操作的代价是操作的数的数量乘以所有数的权值和。问使得所有数 \(\gcd=1\) 的最小代价。\(n\le10^{6}\)，所有数 \(\le10^{12}\)，所有权 \(\le10^{9}\)。

题解：对于 \(\gcd\) 中没有的质数，显然我们不需要考虑。设 \(\gcd\) 中有 \(m\) 个质数，我们去掉它们之外的质数后，打表可知至多只有 \(10000\) 多种数，对于每种数，显然我们取权最小的 \(m\) 个即可。

注意到操作时有两个性质：

• 一种质数要么全删去，要么不删，即不会出现 \(9\div3\) 的情况
• 一种质数只由某一个数操作即可

于是我们可以设 \(dp[i]][j][S]\) 表示目前处理到第 \(i\) 个数，已经操作了 \(j\) 个数，已经删除的质数集为 \(S\)。但是这样复杂度仍然较高，我们还可以记录每个 \(S\) 能够被哪些数操作，只需要前 \(m\) 个即可。

E. Radix sum

题目大意：定义 \(10\) 进制异或为相应位加起来，每位模 \(10\)。现在给你 \(n\) 个 \([0,10^{5})\) 之间的数，对于每个 \(x\in[0,n)\) 问从中选取有序 \(n\) 元组的异或和为 \(x\) 的方案数是多少，模 \(2^{58}\)。

题解：显然我们是要做一个五维，每维长度为 \(10\) 的 FFT。但是 \(1\) 在模 \(2^{58}\) 的意义下没有 \(10\) 次原根。因此我们考虑在模 \(x^{10}-1\) 的多项式环上做 FFT，那么 \(x\) 就是一个 \(10\) 次原根。

根据 wiki 上的描述，我们必须有 \(\sum_{i=0}^{9}x^{i}\) 等于 \(0\)，但是在模 \(x^{10}-1\) 下显然不满足。我们尝试在它的因式中寻找，发现模 \(x^{4}-x^{3}+x^{2}-x+1\) 满足要求。在具体实现时可以模 \(x^{5}+1\)，最后再对 \(x^{4}-x^{3}+x^{2}-x+1\) 取模。