GYM102354 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 题解

· · 个人记录

A. Square Root Partitioning

每个 \sqrt {a_i} 都能唯一表示成 b_i\sqrt {c_i}，其中 c_i 无平方因子。求出这样的表示后，对所有 c_i 相同的 b_i 分别做，然后方案数相乘即可。当 a_i 特别大时，无法快速求出表示。我们考虑随机一些素数 p（假设所有 a_i 都不是 p 的倍数），判断 a_i 是否是模 p 的二次剩余，如果两个数在所有测试中的结果都相同，则认为它们对应的 c_i 相同。如果选择了 k 个素数，则这样的正确率约为 1-\frac{1}{2^k}。对每个 c_i 相同的集合，以及一个满足 c_i 是模 p 的二次剩余的素数 p，对每个 a_i 开根，然后 meet in the middle，就能求出模 p 为 0 的集合个数，这一步的正确率约为 1-\frac{2^n}{p}。

时间复杂度：假设选择了 k 个大小为 p 的素数，则总时间复杂度为 O(nk(\log a_i+\log p)+2^{n/2}n)。

（好像还有更简单的方法，不求出每个 c_i 对应的集合，而是直接做，但是可以 hack。）

B. Yet Another Convolution

如果能在 T(n) 时间内求出 c_1，则可以在 T(n)+T(\frac n2)+T(\frac n3)+\cdots 的时间内解决整个问题。

不妨设 a_i\ge b_j，我们想对每个 a_i，找到最小的 b_j 使得 \gcd(i,j)=1。整体二分，问题转化为判定是否存在 b_j\le M 且 \gcd(i,j)=1。莫比乌斯反演可以得到这样的数的个数为 \sum_{d\mid i}cnt(d)\cdot \mu(d)，其中 cnt(d) 表示 \le M 的 b_j 中，是 d 的倍数的 j 的个数，于是可以在 O(\sum_{i=1}^n d(i))=O(n\log n) 的时间内完成判定。因此，求出 c_1 的时间复杂度为 O(n\log^2 n)，总时间复杂度 O(n\log ^3n)。

C. Money Sharing

把所有借钱的操作按绝对值从小到大排序，能接受就接受，用线段树维护，时间复杂度 O((n+m)\log (n+m))。

D. Magic Strings

当 n\ge 799039879 时答案为 2^{n-799039877}，WTF？n 小的时候就是正常做法，矩阵递推 + 分段打表。

E. Decimal Expansion

找规律发现第 k 段是 89^{2k-1}0^{4k-2}10^{2k}9^{4k}，二分一下在第几段即可，时间复杂度 O(t\log n)。（这个结论可以用五边形数定理证明。）

G. Defying Gravity

合法的直线为图形的对称轴（位置和质量都对称），转化一下就变成了求字符串的回文子串，哈希或 manacher 即可。时间复杂度 O(n\log n) 或 O(129600)。

H. From Modular to Rational

先任意询问两个不同的素数，然后 CRT 合并，得到 q=pX\bmod M，我们要求 1\le p,q\le 10^9，即找到 p 使得 1\le p \le 10^9 且 pX\bmod M\le 10^9。二分 p，则需要检查是否有不超过 L 的 p，注意到这等价于 \lfloor \frac{pX-10^9-1}{M}\rfloor\ne \lfloor\frac{pX}{M}\rfloor，故可以用类欧几里得算法求出等号两边的和并比较。时间复杂度 O(t\log^2p)。

还有一种 O(t\log p) 的做法：要求的即为 \min\{i\ge 0\mid 1\le iX\bmod M\le 10^9\}，考虑求 \min\{x\ge 0\mid l\le ax\bmod p\le r\}，有

I. Tree Automorphisms

以重心为根，若一个点有 k 棵同构的子树，则加入 k-1 个排列，第 i 个排列是交换第 1 棵和第 i+1 棵子树得到的。如果有两个重心则还要考虑相应的两棵子树。