2023.12.10

P9353 [JOI 2023 Final] Modern Machine

不得不说 JOI 出的题的质量还是比较高的，不过我这题基本没有任何思路，鉴定为菜。

首先考虑一次操作干了什么，注意到我们只有在最后一次转弯后的覆盖是有意义的，那么实际上，将结果分为从左边出界和从右边出界，分别造成的修改是前缀染红与后缀染蓝。

那么考虑具体染了多少，大概手动模拟一下发现，如果在第 \(i\) 个位置操作，会将前 \(i\) 个蓝色染红或把后 \(n-i+1\) 个红染蓝。证明也很简单，以前一种情况为例，考虑左边与右边转弯的次数，左边遇到红色会转弯，后边遇到蓝色会转弯，设左边有 \(p\) 个蓝色，那么就有 \(i-1-p\) 个红色，于是会转 \(i-1-p\) 次弯，最后从左边出，说明在右边转了 \(i-p\) 次弯，于是右边覆盖了 \(i-p\) 个蓝色，于是总共覆盖的蓝色数就是 \(i\) 个。

那么暴力模拟这个过程就可以 \(O(nmq)\) 了，可以拿到 \(15\) 分。改成线段树上二分即可 \(O(mq \log n)\)，可以通过第三个包，拿到 \(25\) 分。

考虑第四、五个包怎么做，存在一个 \(t \in [0, n]\)，使得前 \(t\) 个为红色，剩下的都是蓝色。注意到，此时每次操作之后，原来的操作不会改变这个性质，仅改变了 \(t\)，那么我们实际上只需要考虑维护 \(t\) 即可。

简单分情况考虑一下：

若起点 \(i\) 为红色：
- 若 \(n - t \ge i\)，则 \(t \gets t + i\)；
- 否则，\(t \gets t - (n - i) + 1\)；
若起点 \(i\) 为蓝色：
- 若 \(n - t - 1 \ge i\)，则 \(t \gets t + i + 1\)；
- 否则，\(t \gets t - (n - i - 1) + 1\)；

可以发现，上述操作实际上是在模 \(n + 1\) 意义下进行加 \(i\) 或 \(i+1\) 的操作，我们可以写出一个函数 \(f_i(t)\)，表示在 \(i\) 操作下 \(t\) 会变成什么，那么有：

\[f_i(t) = \begin{cases} (t + i + 1) \bmod (n + 1) & t < i\\ (t + i) \bmod (n + 1) & t \ge i \end{cases} \]

那么，我们要求的，实际上就是一个区间内这个函数的复合。对于 \(n = 10\) 的情况，发现我们可以直接维护所有函数值，直接上线段树维护，复杂度 \(O(nq \log m)\)，可以通过第四个包，拿到 \(36\) 分。

直接维护函数值显然是很差的，我们能不能直接维护分段函数？看起来似乎复杂度爆炸，但是注意到我们只有查询操作没有修改操作，于是我们的线段树只要能建出来就行，而查询操作也不需要真的把函数复合找出来，因为我们只要求单点的值，所以查询的时候不需要将线段树上的若干个区间合并起来，于是我们不需要太关心合并两个区间的复杂度，不过我们还是需要关心分段函数的总段数的。

而注意到复合一次这个分段函数相当于进行 \(O(1)\) 次的裁剪拼接，这只会使分段函数增加 \(O(1)\) 段，于是 \(len\) 个函数的复合得到的是一个 \(O(len)\) 段的分段函数，那么我们就可以发现线段树上所有节点上的函数的段数之和是 \(O(m \log m)\) 的。由于合并的时候需要找到分割点的位置，需要二分，所以总建树的复杂度就是 \(O(m \log^2 m)\) 的，单次查询也是 \(O(\log^2 m)\) 的，所以总复杂度 \(O((m + q) \log^2 m)\)，可以通过第五个包，拿到 \(62\) 分。

一般情况呢？注意到，任意局面进行若干次操作后，一定会变成上述的局面，而由于每次操作都是前缀染红与后缀染蓝，我们只需要维护前缀红的数量 \(p\) 与后缀蓝的数量 \(q\)，如果某一时刻两者染的部分交叉了，那么说明此时已经变成了上述的情况。考虑每次操作，如果操作的点 \(i \le p\)，覆盖前缀则 \(p\) 会多覆盖 \(i\) 个蓝点，覆盖后缀则一定会变成前面所述的情况，\(q\) 是同理的，于是对于操作的点在 \(p,q\) 之内的情况，所进行的操作就是一直增加 \(p+q\) 的总和，我们只需要找到什么时候能够交叉即可。

如果操作的点不在 \(p,q\) 之内似乎就不好办了，不过我们注意到，进行一次操作后，无论增长的是 \(p\) 还是 \(q\)，它们都会翻倍，也就是说不在 \(p,q\) 内的点的操作只有 \(O(\log n)\) 次，于是我们只需要每次找到下一次不在 \(p, q\) 内的点，然后判断一下此时应该覆盖前缀还是后缀即可。

但是找 \(p,q\) 内的点是比较麻烦的，因为 \(p,q\) 一直在变。我们可以不严格找到所有 \(p,q\) 之内的点，而是只考虑小于等于 \(p,q\) 的最大的 \(2\) 的幂 \(x,y\)，这样我们只要对每个可能的 \(x,y\) 预处理出 \(i \le x\) 或者 \(i \ge n - y + 1\) 的 \(i\) 或 \(n-i+1\) 的前缀和与下一个 \(x < i < n - y + 1\) 的位置，这样不在 \(x,y\) 内的点仍然只有 \(O(\log n)\) 个，这样我们就可以每次跳一整段，看跳完之后是否 \(p,q\) 仍然不交，不交则找到新的 \(x,y\) 然后继续跳，交了则二分找到段内什么时候开始相交，于是这部分就可以在 \(O(m \log^2 n + q \log n)\) 的时间复杂度内解决了。

那么只需要把两部分拼在一起就做完这道题了。复杂度两个 \(\log\)。代码略有点难写，不过我只写了 5KB，std 命名比较长而且好像写的麻烦了点所以写了 8KB。

2023.12.11

今天 NOIP 一等线出了，全国基准线 199，HE 152，非常有趣。HE 省队名额大概是会骤减不少的了，不过好像按照 HE 的水平来看反而省队名额趋于正常了（

GYM102896F Find a Square

~~做这题纯属因为觉得比较有意思，没有别的原因。~~

但是好像只能想到其中一小部分，果然我的水平不如 water235。

记 \(M\) 为 \(p(x)\) 最大值。

首先答案显然就是要去找若干个质因子的次数之和。注意到如果一个质因子仅出现一次那么这个质因子是没有用的，所以只考虑出现至少两次的质因子。

假如我们现在有一个集合 \(Q\) 为出现至少两次的质因子，那么我们考虑如何计算答案。注意到，\(p(x)\) 是一个二次多项式，根据同余方程的一些理论，对于一个指数 \(p\)，\(p(x) \equiv 0 \pmod p\) 的解数最多只有 \(2\) 个，这可以通过二次方程求根公式加二次剩余找出，但如果 \(2a \bmod p = 0\)，求根公式是解不出来的，而对于这样的质数 \(p\) 仅有 \(O(\log a)\) 个，我们可以直接拿这些数去对所有的整数都试一遍，这部分复杂度 \(O(n \log a)\)。对于 \(Q\) 中剩下的数，我们只需要考虑所有是 \(p\) 的倍数的值，这一共有 \(O(\sum \lceil \frac{n}{p} \rceil) = O(n \log M + |Q|)\) 个。

那么现在问题就是 \(Q\) 中哪些数。由于我们现在仅考虑出现次数至少两次的数，那么我们可以分两种情况考虑：一个质因子仅在同一个数中出现过，或者一个质因子出现在超过两个数中。在此之前，我们可以先将所有 \(O(M^\frac 13)\) 的质因子给除掉，此时剩下的每个数中最多只有两个质因子。如果一个质因子在同一个数中出现，那么这个数一定是完全平方数，我们把所有的数判断一下即可，那么此时剩下的所有数要不然是大质数，要不然是两个不同的质数相乘。那么此时我们仅需要考虑第二种情况，也就是只关心所有出现在至少两个数内的质因子。

考虑两个数 \(p(i), p(j)\)，假如两者均为 \(p\) 的倍数，那么其差一定也是 \(p\) 的倍数，那么作差后可以得到 \(p | a (i^2 - j^2) + b (i - j)\)，即 \(p | (i - j) (a (i + j) + b)\)。注意到前者一定是 \(O(n)\) 级别的数，而后者一定形如 \(ax+b\)，前者可以找出所有 \(O(n)\) 的质数加入 \(Q\)，后者可以使用与二次类似的想法，对于任意一个质数 \(p\) 来说，\(a x + b \equiv 0 \pmod p\) 最多有 \(1\) 个解，那么我们可以枚举 \(O(n)\) 内的所有质数，将其除去，剩下的所有 \(ax+b\) 要不然是 \(1\)，要不然剩下一个大于 \(O(n)\) 的质数，把这 \(O(n)\) 个质数加入 \(Q\) 即可，这部分与二次的复杂度一样，\(O(n \log n)\)。

注意上述复杂度均没有乘上找一个数内有多少质因子的数量，不过这部分平均除的次数不多，所以忽略不记。

发现我连二次剩余都不会求，所以再写个二次剩余的做法：

求解 \(x^2 \equiv a \pmod p\)。

欧拉判别法：若 \(a^{\frac{p - 1}{2}} \equiv 1 \pmod p\)，则 \(a\) 是二次剩余，若 \(a^{\frac{p - 1}{2}} \equiv -1 \pmod p\)，则 \(a\) 是二次非剩余。

考虑找到一个数 \(r\)，使得 \(r^2 - a\) 不是二次剩余，那么我们可以扩域，定义 \(i^2 \equiv r^2 - a \pmod p\)，一个数可以用 \(a + bi\) 表示，乘法容易写出。有结论：\(a \equiv (r + i)^{p+1} \pmod p\)，即 \(x \equiv \pm (r + i)^{\frac{p+1}{2}} \pmod p\)。

证明：

\[\begin{aligned} (r+i)^{p + 1} &= (r+i)^p (r+i)\\ &= (r^p + i^p) (r + i)\\ &= (r - i)(r + i)\\ &= r^2 - i^2\\ &= a \end{aligned} \]

第一步直接二项式定理容易得到，第二步是由欧拉判别法可得 \(i^p = i i^{p-1} = i (r^2-a)^{\frac{p-1}{2}} = -i\)。

而由于二次非剩余有 \(\frac{p-1}{2}\) 个，所以期望随机两次即可找到一个二次非剩余，于是我们就可以在 \(O(\log p)\) 的复杂度内解决二次剩余问题。

P6730 [WC2020] 猜数游戏

简单题..？好像真的不难。

首先都有 \(a_k^m \bmod p\) 了，保证质数是 \(p^k\)，还有个特殊性质是 \(3^i \bmod p\) 互不相同，原根都糊脸上了。把原根找出来，设它是 \(g\)。

先考虑模数为奇素数 \(p\) 的情况，那么此时所有数都存在离散对数，那么跑个离散对数出来，设 \(a_i \equiv g^{b_i} \pmod p\)。考虑题目实际上就是，每个数有若干覆盖范围，对于所有可能集合用最少的数覆盖整个集合。发现取完离散对数之后，覆盖的数就是所有 \(\gcd(b_i, \varphi(p))\) 的倍数。注意到这是满足偏序关系的，即如果 \(i\) 能覆盖 \(j\)，\(j\) 能覆盖 \(k\)，那么 \(i\) 也能覆盖 \(k\)，那么如果我们把覆盖的关系建成一个图，那么这个图一定是 DAG，那么问题就很简单了，我们只需要选择所有入度为 \(0\) 的点就行了。计算期望也就很简单了，根据线性性，我们考虑每个点入度为 \(0\) 的概率，发现只要所有入度都不在集合里就行，所以概率就是个 \(2^{-c}\) 一类的东西。那么只需要把所有连边关系找出来就行了。这里偏序关系需要特别定义一下，因为有可能两个 \(i,j\) 的 \(\gcd(b_i, \varphi(p))\) 相同，此时我们定义编号较小的那个偏序关系较小，而 \(\gcd\) 不相同的定义 \(\gcd\) 之间的整除关系为偏序关系即可。\(O(n^2)\) 容易实现。

考虑模数为 \(p^k\) 怎么做，发现此时多出了一些数是 \(p\) 的倍数，这些数不存在离散对数，注意到 \(p\) 的倍数的次幂一定都是 \(p\) 的倍数，不是 \(p\) 的倍数的次幂也一定都不是 \(p\) 的倍数，所以两部分可以分开计算。考虑设 \(c_i\) 为 \(a_i\) 中 \(p\) 的质因子的次数，注意到它的次幂的 \(c\) 一定比当前大，于是这仍然是一个 DAG，于是我们可以使用同样的方法去计算，问题在于如何快速判断 \(a_i\) 能不能覆盖 \(a_j\)。注意到，如果 \(a_i\) 能覆盖 \(a_j\)，那么假如 \(a_i ^ m = a_j\)，那么 \(c_j = m c_i\)，这样我们就可以快速得到 \(m\)，那么判断就很容易了。

离散对数不能直接 \(O(p)\) 计算，会炸空间，写个 BSGS 即可，复杂度 \(O(n \sqrt{p} + n^2)\)。

CF1110G Tree-Tac-Toe

这是真简单题。简单分类讨论即可。

简单分析下，发现这里面有极多先手必胜策略。

如果有点的度数 \(\ge 4\)，那先手必胜，先手下中间然后依次选叶子即可；
如果有点的度数 \(=3\)：
- 如果这个点是白色，那先手必胜；
- 如果有一个相邻的点是白色，那先手必胜；
如果存在一条长度为 \(4\) 且中间一个点为白色，则先手必胜；
如果存在一条长为 \(5\) 且中间一个点度数为 \(3\)，则先手必胜；
如果有相邻两个白色点则先手必胜。

在进行以上分析之后，发现，上述条件均不满足的情况，一定满足：

只有叶子才可能是白色；
大致形如一条链，只有链的两端有可能为以下三种情况之一：
- 一个三度点，相连的点均无颜色；
- 一个无颜色叶子；
- 一个白色叶子。

注意需要把 \(n=4\)，有一个三度点的情况特判掉。

那么接下来我们只需要分析这几种情况的先手必胜策略了。

一条链，仅有一端是白色 / 没有白色：显然先手是没有必胜策略的，此时一定平局；
一条链，两端都有白色：首先注意到 \(n=3\) 先手必胜，\(n=4\) 平局，猜测奇数必胜偶数必败。发现，如果是奇数，每次可以选一边靠近叶子的第三个位置，这样后手必须去堵上中间的位置，否则先手就胜利了，那么此时 \(n\) 减少 \(2\)，说明一定可以先手必胜。同理，如果是偶数，先手选择任意一个位置，都会把链分成一奇一偶，而后手只需要堵在奇数的一边，这样奇数一边得到的是第一种情况，先手没有必胜策略，偶数一边递归，于是最终一定平局；
一边是三度点一边是白色：与上一个情况分析类似，发现 \(n\) 为偶数时先手必胜；
两边都是三度点：与上一个情况分析类似，发现 \(n\) 为奇数时先手必胜。

剩下的没提到的情况就全都是平局。