WC2020

有根树

猜数游戏 \((\texttt{Easy} \ 1 / 3)\)

首先考虑 \(p\) 是质数的情况。

找到一个 \(p\) 的原根 \(g\)，设选的数为 \(x_1, x_2, \cdots, x_k\)，我们令 \(x_i \equiv g^{w_i} \pmod p\)（这一步用 BSGS 求出，要手写哈希表），那么发现选择 \(x_i\) 可以覆盖 \(g^v\) 当且仅当 \((w_i, p - 1) \mid w_i - v\)。

于是我们显然可以按照 \((w_i, p - 1)\) 从小到大选数，相同的时候按照 \(a\) 从小到大选，不难证明这样是最优的。那么对于一个数 \(a_i\) 存在一个固定的集合 \(S_i\)，若选出的 \(x\) 都不在 \(S_i\) 内，则 \(a_i\) 必然会被选。这个集合可以在 \(\mathcal{O}(n^2)\) 的时间复杂度内统计出。

对于 \(p = q^k\) 的情况，发现不是 \(q\) 的倍数和是 \(q\) 的倍数分开考虑。不是 \(q\) 的倍数的情况和上面一样，只是 \(p - 1\) 变为了 \(\varphi(p)\)。对于是 \(q\) 的情况，令 \(a_i = v \times q^t\)，那么我们发现这一部分肯定是按照 \(t\) 从小到大选更优，而 \(t\) 相同的也不相互影响，所以 \(a_i\) 会被选当且仅当选出的数中不存在 \(x = v' \times q^{t'}\)，使得 \(t' \mid t\) 且 \(x^{\frac{t}{t'}} \equiv a_i \pmod p\)。于是这一部分也可以做了。

总的时间复杂度是 \(\mathcal{O}(n^2 + n \sqrt p)\)。

能不能再给力一点啊？

首先 \(q \mid a_i\) 的情况可以直接枚举 \(a_i\) 的幂次。对于 \((a_i, p) = 1\) 的情况，发现 \(w_i\) 不重要，而 \((w_i, \varphi(p))\) 重要。我们使用试除法求出 \(a_i\) 模 \(p\) 的阶 \(r\)，那么 \((w_i, \varphi(p)) = \frac{\varphi(p)}{r}\)。然后我们发现 \((w_i, \varphi(p)) \mid w_i - v\) 等价于 \((w_i, \varphi(p)) \mid v\)，因为 \(w_i\) 一定是 \((w_i, \varphi(p))\) 的倍数，所以第一种情况的统计可以直接高维前缀和。

这个算法的时间复杂度是 \(\mathcal{O}(n \Omega(p) \log p + p^{\frac14})\)。

选课 \((\texttt {Easy} \ 3 / 6)\)

根据题面中对数据范围的提示，题解中 \(p\) 的意义为受限制的课程个数、\(T\) 自动和 \(\sum s_i\) 取 \(\max\)。

和网上的主流做法不同，本做法基于一个引理。

• 引理：转移方程式形如 \(f_{i, j} = \max\limits_{k = 1} ^ {w_i} \{f_{i - 1, j - k} + v_{i, k}\}\) 的 DP，令函数 \(f_i(j) = f_{i, j}\)，那么 \(f_i(x)\) 对 \(x\) 在模 \(\max w_i!\) 分组下是上凸的。

证明好像不太简单，我不会在此略去。

先考虑 \(p = 0\) 的情况。我们知道两个凸包的和可以用闵可夫斯基和做到 \(\mathcal{O}(n)\) 合并，所以可以先把每个种类的课的 DP 数组先分治预处理出来，然后因为 \(T - \sum s_i\) 很小可以暴力合并。

对于 \(p > 0\) 的情况，直接暴力枚举每一门受限制的课程的选择情况。对于每一种选择情况，先判断是否符合第三个要求，然后前两种的 \(c\) 最后加上，它们贡献的学分实际上是 DP 数组的平移，可以先把没有受限制的课程种类 DP 数组先合并，对于有特殊课程的课程种类报了合并即可，类似皮配。

时间复杂度算不太清楚，能过 只不过大概率是最裂解。

代码暂时咕掉了，因为主要是想学一下这个套路所以只写了 \(p = 0\) 的代码。 代码还是写了，果然荣获最裂解。