CodeTON Round 3

最近太摆了，补题

Source

CodeTON Round 3

A - Indirect Sort

我们发现，$a_1$ 是不会增大的。故若 $a_1$ 不是最小值，不可能将 $\lbrace a\rbrace$ 变成不降的

而若 $a_1$ 是最小值，操作 2 就变成了交换 $a_j, a_k$，就是普通的 swap 操作，因而一定可以调整为不降的

Code

1750 A

B - Maximum Substring

模拟即可

Code

1750 B

C - Complementary XOR

注意到，每一次的操作会让全部的 $|a_i - b_i|$ 取反，这意味着如果初始状态 $|a_i - b_i|$ 不全都相等的话，不可能做到

方便起见，如果 $|a_i - b_i| = 1$，进行一次操作，使得 $a_i = b_i$

接下来进行 $n - 1$ 次操作让 $a_i$ 全部变得相等。此时会有四种情况：

• $a_i = 1, b_i = 0$
• $a_i = 1, b_i = 1$
• $a_i = 0, b_i = 0$
• $a_i = 0, b_i = 1$

操作方法显然，讨论一下即可

Code

1750 C

D - Count GCD

显然 $b_1 = a_1$

令 $f(i)$ 表示 $i$ - 前缀的答案，有 $f(1) = 1$ 及转移

$$f(i) = f(i - 1) \times g(i)\bmod p$$
其中 $g(i)$ 表示满足 $\gcd(x, a_{i - 1}) = a_i$ 的 $x$ 的个数

由于一定有 $a_i | a_{i - 1}$，取 $q = a_{i - 1} / a_i$

• 若 $q = 1$，$g(i) = \lfloor\dfrac{m}{a_i}\rfloor$
• 若 $q\neq 1$，则应满足 $x = ka_i$，其中 $\gcd(k, q) = 1, k\leq\lfloor\dfrac{m}{a_i}\rfloor$

问题转化为求 $\left[1, \lfloor\dfrac{m}{a_i}\rfloor\right]$ 中与 $q$ 互质的数的个数

考虑容斥原理。得到 $q$ 的质因数后，使用二进制来枚举因数，使用 popcount() 来计算系数正负。以前没用过，看到二进制枚举豁然开朗

Code

WA + RE 了 8 发，写在 Warnings 里面了

1750 D

Warnings

• 开 long long
• 注意自己在 init() 里到底写了啥，这次是疯狂重复 Euler 筛
• 注意一些 Global Variable 的变化情况，这次是 cntPrime 疯狂变大导致 RE
• 当发现把数组开大就能多过几个原先 RE 的点时，注意自己数组访问的问题

Postscript

R.I.P.

当我还是一名 OIer 的时候，玩的最多的就是膜蛤、续命、决赛圈的梗

熬过了地图头、送走了英女王，长者终于停下了已迈入决赛圈中的脚步

1926.08.17 - 2022.11.30

是谁禁止了军队经商
是谁平治了洪水汤汤
是谁稳定了通货膨胀
是谁坚持了改革开放
是谁任命了铁血宰相
是谁摧毁了邪教道场
是谁收回了澳门香港
是谁平息了金融巨浪
是谁加入了世界商贸
是谁提出了科教兴邦

苟利国家生死以，岂因祸福避趋之

功名半纸，风雪千山