本来想打的，但是太晚了，就摆烂睡大觉打算vp了，vp还打了1h又摆去睡大觉了，摆烂人摆烂魂，摆烂人就是……法王了属于是。
C. Koxia and Number Theory
简要题意
给定一个长度为 \(n\le100\) 的正整数序列 \(a\) ，判断是否存在一个 \(x>0\) 使得以下条件成立：
- \(\text{gcd}(a_i+x,a_j+x)=1,\forall 1\le i<j\le n\) 。
题解
我们首先瞎猜一个结论，只要序列中没有相同的数并且 \(\min\{\text{奇数个数},\text{偶数个数}\}\le1\) ， 答案就是 \(\text{Yes}\) ，否则就是 \(No\) ，然后你撸了一份代码，过了样例 ，就过了这题 ，就完美地 \(\color{red}\text{WA}\) 了，然后让我们冷静冷静，来认真分析一下这题的性质。
众所周知 \(\text{gcd}\) 有非常好的性质 \(\text{gcd}(a_i+x,a_j+x)=\text{gcd}(a_i+x,|a_i-a_j|)\) ，那么我们固定 \(i\) 考虑 \(\forall j>i\) ，题目中的条件就是 \(\text{gcd}(a_i+x,|a_i-a_j|)=1,\forall j>i\) ，稍加思索我们便发现这等价于 \(a_i+x\) 没有任何的一个 \(|a_i-a_j|\) 的质因子，那么我们可以对所有 \(|a_i-a_j|\) 做质因数分解找到质因子 \(p\) ，那么 \(a_i+x\ne 0(mod\ p)\) 即为 \(x\ne -a_i(mod\ p)\) ，那么我们开个 \(\text{map}\) 记录一下对于每个质数的不可选系，如果有某个质数的不可选系占满了 \(Z[p]\) ，那么答案就是 \(No\) ，否则就是 \(Yes\) ，原因也很简单，如果每个 \(Z[p]\) 中都有可选的数，我们很容易就可以通过 \(\text{CRT}\) 构造出一个合法的 \(x\) 。
复杂度为 \(O(n^2k)\) ，其中 \(k\) 为整数分解复杂度，在实现上要求较快的整数分解方法，使用 \(\text{Pollard-rho}\) 可以通过。
或者你不那么暴力，注意到实际上 \(>n^2\) 的质数肯定不会被占满，那么你只需要对于 \(\le n^2\) 的 \(p\) 统计即可，时间复杂度 \(O(n^4)\) 或者跑一个欧拉筛 \(O(n^2\pi(n^2))\) 。这个应该才是正解，什么 \(\text{Pollard-rho}\) 都是瞎搞。
D. Koxia and Game
简要题意
令 \(S\) 为三元组 \(\{a_i,b_i,c_i\}\) 的大小为 \(n\le10^5\) 的可重集，有两个人 \(A\) 和 \(B\) 玩游戏，每次 \(A\) 挑选 \(S\) 中的一个未挑选的三元组并删除其中一个数，之后 \(B\) 在剩余两个数中选择一个数，经过 \(n\) 轮后 \(B\) 得到了一个 \(n\) 个数的集合，如果该集合包含 \(1\sim n\) ，那么 \(B\) 就获胜，反之则 \(A\) 获胜。
给定 \(a_i\) 和 \(b_i\) ，问有多少种 \(c_i\) 使 \(B\) 有必胜策略。
题解
套路，先分析给定 \(S\) 的情况下什么时候 \(B\) 获胜。样例一启发我们发现有 \(2\) 个相同的数的三元组是关键的，因为在这种情况下 \(B\) 可以确保拿到那个数。手模样例一我们发现当且仅当 \(n\) 个三元组都有 \(2\) 个相同的数且这些数取遍 \(1\sim n\) \(B\) 才能赢。
作为尝试，我们考虑这个结论是不是对的。充分性显然， \(B\) 可以保证拿到 \(1\sim n\) 中所有数，则其必胜。考虑必要性，如果有一组没有 \(2\) 个相同的数或者相同的数没有取遍 \(1\sim n\) ，那么 \(B\) 确保能拿到的数肯定有缺失，设其为 \(x\) ，由于 \(x\) 在所有三元组中最多出现 \(1\) 次， \(A\) 只需要把所有三元组中的 \(x\) 拿走， \(B\) 就赢不了游戏，于是必要性得证。
至此我们已经找到了 \(B\) 获胜的条件，即 \(n\) 个三元组都有 \(2\) 个相同的数且这些数取遍 \(1\sim n\) ，考虑如何求出方案数。
如果 \(a_i=b_i\) ，那么 \(a_i\) 已经进入 \(B\) 的集合，如何选择 \(c_i\) 对这个三元组没有影响，对答案的贡献就是 \(\times n\) 。如果 \(a_i\ne b_i\) ，那么我们肯定只会在 \(\{a_i,b_i\}\) 中选择 \(c_i\) ，否则不优，那么这个操作就相当于我们钦定了一个 \(a_i,b_i\) 加入 \(B\) 的集合中。二选一的性质启发我们通过图论边定向的观点看这个问题，我们对所有 \(a_i,b_i\) 连边 \(e(a_i,b_i)\) ，那么在图中，度数为 \(1\) 的节点所连的边方向确定，所有能确定的边都确定完后，留下的就是环，但是如果有两个环并未完全分离，就是两个环可达，这种情况显然无解，只有环分离的情况下才有解，每个环对答案的贡献为 \(\times 2\) ，于是我们就解决了这道题。
E. Koxia and Tree
简要题意
给定一棵 \(n\) 个节点的树，其中 \(k\) 个关键点上有硬币，对所有树边随机定向后按输入顺序做如下操作：
- 设这条边为 \(u\rightarrow v\) ，如果 \(u\) 上有硬币而 \(v\) 上没有，那么就把 \(u\) 上的硬币移动到 \(v\) 上。
经过 \(n-1\) 次操作后我们得到了全新的 \(k\) 个关键点，之后从 \(k\) 个点中随机取 \(2\) 个点，求这 \(2\) 个点距离的期望。
题解
我们先来考虑没有移动操作如何求出 \(k\) 个点随机选 \(2\) 个点的距离的期望，考虑期望 \(E=\dfrac{\sum_{i,j}\text{dis}(i,j)}{\text{方案数}}\) ，方案数为 \(\dbinom{k}{2}\) 容易求出，考虑如何求 \(\sum\text{dis}\) ，这也是个经典问题，对边算贡献，每条边的贡献为 \(sz_{left}\cdot sz_{right}\) ，其中 \(sz\) 定义为关键点数量，那么 \(\sum\text{dis}=\sum_{e_i}sz_i(k-sz_i)\) 。
加入移动操作，如果我们能求出子树每个 \(sz\) 的概率 \(p\) ，一条边的对总期望的贡献就能算出为 \(\sum sz\cdot(k-sz)\cdot p\) ，考虑如何求出这个 \(p\) 。经过观察我们发现一个关键性质，子树的 \(sz\) 变化只与子树根节点到父亲节点的那条边的行为有关，有 \(|\Delta sz|\le1\) ，那么最多只有 \(3\) 种不同的 \(sz\) ，大大减轻计算复杂度。我们关注这条边的行为，如果我们能够知道在这条边定向前一刻，两点为关键点的概率 \(p_u\) 和 \(p_v\) ，这条边对子树 \(sz\) 的贡献就能够被计算，假设 \(u\) 为 \(v\) 父亲则有概率：
- \(\Delta_{-1}=\dfrac{p_v(1-p_u)}{2}\)
- \(\Delta_1=\dfrac{(1-p_v)p_u}{2}\)
- \(\Delta_0=1-\Delta_{-1}-\Delta_1\)
于是就有对答案贡献 \(\sum\limits_{i=-1}^1(sz+i)\cdot(k-(sz+i))\cdot\Delta_i\) 。
那么问题就转化为了求任意时刻每个点为关键点的概率，初始状态肯定是 \(p_i=1/0\) 由输入决定，考虑一条边 \(e(u,v)\) 的影响，经过讨论可知这条边操作后 \(p_u'=p_v'=\dfrac{p_u+p_v}{2}\) ，于是这题就做完了。
别看这思路这么清晰，场上大概率绕不少弯路……