Contest Info

date: 2018.06.29 09:00-14:00

practice link

Solutions

B. Master of Phi

签到题。

C. Hakase and Nano

题目大意：将 Nim 游戏的规则改为其中一个人（h）每次必须连续进行两次操作（最后一次除外），拿到最后一颗石子的人胜。分析 h 在不同先后手情况下的输赢情况。

题解：

• 若每堆石子都只有 \(1\) 颗

  • 若 h 先手，则 \(n\equiv0\pmod{3}\) 时 h 负，否则 h 胜。
  • 若 h 后手，则 \(n\equiv1\pmod{3}\) 时 h 负，否则 h 胜。

• 若恰有 \(1\) 堆石子多于 \(1\) 颗，其余每堆石子都只有 \(1\) 颗

  • 若 h 先手，则 h 必胜。他有两种不同的选择：将那堆石子分两次取完，或者一次取完后再取另外一堆石子。这两种选择得到的新 \(n\) 恰好相差 \(1\)，必有一种是 h 的胜态。
  • 若 h 后手，则 \(n\equiv2\pmod{3}\) 时 h 胜，否则 h 负。\(n\equiv0\pmod{3}\) 时，另一个人可以将那一堆石子取到只剩 \(1\) 颗；\(n\equiv1\pmod{3}\) 时，另一个人可以将那堆石子全部取走；否则他不论怎么取都是 h 的胜态。

• 若多于 \(1\) 颗石子的堆数大于 \(1\)

  h 必胜，我们归纳地证明这一结论：

  • 若 h 先手
    • 若恰有 \(2\) 堆石子多于 \(1\) 颗，其余每堆石子都只有 \(1\) 颗。h 有两种不同的选择：将两堆石子都取完，或者取完一堆石子，另一堆石子取到只剩 \(1\) 颗。这两种选择得到的新 \(n\) 恰好相差 \(1\)，必有一种是 h 的胜态。
    • 若多于 \(2\) 堆石子多于 \(1\) 颗。h 可以分两次取完一堆石子，必然是他的胜态。
  • 若 h 后手，由于另一个人只能操作一次，因此他取完后至少还有一堆石子大于 \(1\) 颗，这必然是 h 的胜态。

G. Marriage

题目大意：有 \(n\) 个家族，每个家族有 \(a_{i}\) 个男子和 \(b_{i}\) 个女子，\(\sum_{i=1}^{n}a_{i}=\sum_{i=1}^{n}b_{i}\)，求他们结婚的方案数，要求同一个家族的人不能结婚。

题解：容斥。设 \(f(i)\) 表示选取 \(i\) 对同家族结婚的方案数，那么显然答案为 \(\sum_{i=0}^{sum}(-1)^{i}f(i)(sum-i)!\)。

下面考虑如何求 \(f(i)\)。显然不同家族之间互不影响，那么有 \(f(i)=\sum_{\sum_{j=1}^{n}t_{j}=i}\prod_{j=1}^{n}g(t_{j})\)，其中 \(g(t_{j})={a_{j}\choose t_{j}}{b_{j}\choose t_{j}}t_{j}!\)。容易发现 \(f\) 是一个卷积形式，可以用 \(NTT\) 加速。做多项式乘法的时候，我们可以采用哈夫曼的思想，每次将次数最小的两个多项式合并，容易证明这样的复杂度为 \(\mathcal{O}(n\log^{2}n)\)。

H. Master of Connected Component

题目大意：给定一个初始只有 \(m\) 个点，没有边的图 \(G\)，和两棵均以 \(1\) 为根的树 Ta 和 Tb。树 Ta 和 Tb 上每个点存储的是图 \(G\) 中的一条边。

现在问你对于 \(\forall i, i \in [1, n]\)，把两棵树中，点 \(i\) 到根的两条路径上所有点存储的边插入图 \(G\)，有多少个连通块。

题解：我们按照 SCOI 王室联邦的树分块方法，把两棵树各分为 \(\sqrt n\) 块。这种分块方法下，每一块要么连通，要么加上它们的 lca 之后连通。我们用这个 lca 来代表这个块，那么显然 lca 也只有 \(\sqrt n\) 个。

考虑两棵树的所有块的 lca，这样的 pair 只有 \(\sqrt n \times \sqrt n = n\) 类。我们将询问分类，对于每一类进行处理。处理这一类的时候，我们先把图 \(G\) 的状态转移到两棵树对应的 lca 处。然后处理每一个询问，处理完每个询问的时候，都用可撤销的启发式合并并查集恢复状态，以供下个询问。

这样，在类的内部，每个询问最多转移 \(\mathcal{O}(\sqrt n)\) 次。考虑类之间，我们在两棵树中把各自块的 lca 打上标记，然后 dfs 第一棵树，对于有标记的点，我们从头开始 dfs 第二棵树。这样的复杂度是 \(\mathcal{O}(n\sqrt n)\) 的。

J. Master of GCD

签到题。

K. Master of Sequence

题目大意：给定 \(a_{i}\) 和 \(b_{i}\)，每次操作可能修改某个 \(a_{i}\) 或某个 \(b_{i}\)，也可能给出一个 \(k\)，询问满足 \(\sum_{i=1}^{n}\lfloor\frac{t-b_{i}}{a_{i}}\rfloor\ge k\) 的最小的 \(t\)。

题解：显然二分答案，考虑对于一个 \(t\) 如何快速计算左边的和式。下面为了方便，将所有的 \(b_{i}\) 取反。 \[ \begin{aligned}\\ &\sum_{i=1}^{n}\lfloor\frac{t+b_{i}}{a_{i}}\rfloor\\ =&\sum_{i=1}^{n}\lfloor\frac{t\%a_{i}+b_{i}\%a_{i}}{a_{i}}\rfloor+\lfloor\frac{t}{a_{i}}\rfloor+\lfloor\frac{b_{i}}{a_{i}}\rfloor\\ =&\sum_{i=1}^{n}\lfloor\frac{t}{a_{i}}\rfloor+\sum_{i=1}^{n}\lfloor\frac{b_{i}}{a_{i}}\rfloor+\sum_{i=1}^{n}\lfloor\frac{t\%a_{i}+b_{i}\%a_{i}}{a_{i}}\rfloor \end{aligned} \] 注意到 \(a_{i}\) 的范围很小，我们可以对每种不同的 \(a_{i}\) 分别计算。和式的前两项都容易 \(\mathcal{O}(1)\) 地更新和查询。第三项，显然有 \(b_{i}\%a_{i}\in[a_{i}-t\%a_{i},a_{i})\) 时取 \(1\)，其它时候取 \(0\)，也就是说我们只需要维护一个后缀和即可。考虑到本题的数据范围，\(\mathcal{O}(a_{i})\) 暴力更新，\(\mathcal{O}(1)\) 查询更优。

时间复杂度 \(\mathcal{O}(n+a^{2}_{i}+ma_{i}+qa_{i}\log ka_{i})\)。

L. Mod, Xor and Everything

题目大意：求 \(\bigoplus_{i=1}^{n}n\%i\)。

题解：首先根号分块，设该块为 \([i,j]\)。易知所求即为 \(\bigoplus_{k=0}^{j-i}\lfloor\frac{n}{j}\rfloor k+n\%j\)。考虑分别求结果的每一个二进制位，对于第 \(u\) 位来说，答案恰为 \((\sum_{k=0}^{j-i}\lfloor\frac{\lfloor\frac{n}{j}\rfloor k+n\%j}{2^{u}}\rfloor)\&1\)，这样就转化成了一个类欧几里得算法。由于对于每一段需要做 \(\mathcal{O}(\log n)\) 次类欧，常数较大，因此区间较小时应当暴力。

时间复杂度 \(\mathcal{O}(\sqrt{n}\log^{2} n)\)。