kblack edited 6 年前
kblack: Huge gap expected. （唔，好像真的惨案了）
| # | Tag | Idea | Developer | Tester |
|---|---|---|---|---|
| A | 脑洞 | 改编自 GP of Shenyang 2018 I | ultmaster | oxx1108 |
| B | 模拟 | ultmaster | ultmaster | kblack |
| C | 几何 数学 | oxx1108 | ultmaster | oxx1108 |
| D | 分类讨论 | oxx1108 | ultmaster | zerol oxx1108 |
| E | 图论 DP | oxx1108 | ultmaster | zerol |
| F | 离散对数 分块 | kblack | kblack | zerol |
这题的整个题面都几乎和沈阳一样。但是问题完全不一样。
动动脑子，很容易构造出 $n \ 0 \ n \ 0 \ 0 \ 0$ 或者类似的形式。
但是：
把数当成 26 进制的整数，就会发现把小的那个数加 1 就可以。
实现一个类似于大数加法的东西。
距离平方为奇数是不行的。证明略。
距离平方为偶数时，要么中点是一个整点（就做完了），要么 $x$ 坐标和 $y$ 坐标都不是整数。这时，把 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的向量 $(x,y)$ 除以 $x,y$ 的 gcd，然后除以 2，旋转九十度，加到中点上，会产生两个坐标。输出小的那个就好了。
分两种情况讨论：
实现的时候比较容易写错，而且有点没法调试。
对于图的每一个连通块，进行二分图染色之后可以看出是一个典型的背包问题。（就是要么选 A 要么选 B 的那种问题，那么可以假设全选小的那块，然后对差值进行背包）。物品数量高达 $n$，重量目标高达 $n$，但是物品重量和也只有 $n$ 的级别。很容易看出，物品种类只有 $\sqrt{n}$。所以可以尝试用多重背包来解决。
考虑多重背包经典的队列优化，对于剩余系下的每个可能的情况都维护一个队列表示之前出现的位置。在此问题中，我们甚至可以抛弃队列，我们只需要知道在模 $w$ 为 $r$ 时，最后一个可行的状态是谁。如果当前在计算的状态从不可达变成了可达，我们就要更新当前状态的 pre。这样就可以在 $O(n \sqrt{n})$ 时间内背出来并回溯出方案。
方案回溯完了以后还要回溯二分图的方案。。。真的有点胖。。。
解法二：
$$
\begin{eqnarray}
\frac {c(10^x-1)} 9 &\equiv& k &\pmod p \
c \cdot 10^x &\equiv& 9k+c &\pmod {9p} \
\end{eqnarray}
$$
如果 $gcd(c,9p)=1$，那么只要两边同时乘 $c$ 关于 $9p$ 的逆元即可。否则设 $gcd(c, 9p)=t$，如果 $t \nmid 9k+c$ 就无解了，所以可以在等式两边同时除以 $t$。现在问题转化成了求 $10^x \equiv a \pmod {q}$ ，可以用扩展大步小步（exBSGS）求解，注意到最小解肯定不会超过 $p$，所以步长设置在 $\sqrt p$ 就够了，如果用了 $\sqrt q$ 可能会超时。
解法一：
不会 exBSGS？我们换个角度推一遍。定义 $f(x) = \overbrace{ cc \cdots c }^{ x }$，选择一个分块大小 $m = \sqrt p$。
$$f(x) = f(x \bmod m) \times 10^{\lfloor\frac{x}{m}\rfloor \times m} + f(\lfloor\frac{x}{m}\rfloor \times m)$$
我们就可以枚举 $\lfloor\frac{x}{m}\rfloor$，后面的部分和前面的部分都可以递推得到，一番整理后，于是问题转化为求解 $f(x) \times 10^A \equiv C \pmod p)$，然而 $10$ 对 $p$ 并不一定有逆元，这就很尴尬，只能快乐 CRT。对于较小 $x$ 我们暴力枚举判断，对于较大的 $x$，考虑到 $p$ 中 $2,5$ 不多，另 $p’$ 为除去 $p$ 中所有 $2,5$ 因子的结果，转化为方程组
$$
\begin{eqnarray}
C \equiv 0 \pmod {\frac{p}{p’}} \
C \equiv f(x) \times 10^A \pmod{p’}
\end{eqnarray}
$$
这下就可以快乐逆元了，于是我们近似发明了一遍 exBSGS 解决了这道题。
// 看着整页的暴力好心痛。
恭喜 Grunt1997 , palayutm , Kilo_5723 喜提冠亚季军。
出题人要工作。证明在路上了。
把中垂线方程列出来然后把分母扔掉后会发现有一项是奇数，其余都是偶数。