Atcoder Regular Contest 127
$\text{ARC}$ 真的比 $\text{div2}$ 难好多啊, 思维性太强了.
前三题主要是注意写法, 想到应该并不难.
$\text{[ARC127D]Sum of Min of Xor}$
$\color{green}{\text{[EASY]}}$
其实质是判断每对 $i,j$ , $a_i \oplus a_j$ 和 $b_i \oplus b_j$ 哪个更大.
二进制下的判断大小重点是找到最高的不同的二进制位, 而这一位很好找, 就是 $a_i \oplus a_j \oplus b_i \oplus b_j$ 的最高位.
于是可以预处理 $c_i = a_i \oplus b_i$ , 然后分治处理即可.
$\text{[ARC127E]Priority Queue}$
$\color{blue}{\text{[NORMAL]}}$
虽然看着触手可及, 但实际上思维难度还真不低.
不难想到第 $i$ 次插入 $i$ 这个数, 得到的数列是最终局面里面字典序最大的, 设其为 $z$ .
那么就出现了一个必要条件, 对于一个最终局面的排列 $x$ , 有 $x_i \leqslant z_i$ .
不难证明这个条件也是充要的.
于是 $\mathcal{O}(A^2)$ $dp$ 即可.
设 $f_{i,j}$ 表示考虑前 $i$ 个数, 最后一个数不超过 $j$ 的方案数, 前缀和优化即可.
$\text{[ARC127F]}\pm\text{AB}$
$\color{red}{\text{[HARD]}}$
结论啥的真不难猜, 但最后类欧几里德真难编.
结论 $1$ : 若 $a+b \leqslant m+1$ , 则答案为 $m+1$ .
由裴蜀定理, 必然存在 $pa+qb = 1$ , 所以必然可以取到 $a,b$ 里面的任意一个, 然后 $[0,m]$ 就都可以取到了.
特判这个情况后有 $a+b \geqslant m+2$ .
考虑一次操作 $+a$ 之后, 不可能再 $-a$ , 因为没意义, 也不可能是 $+b$ , 因为会超过 $m$ , 所以只可能是 $+a$ 或者 $-b$ , 对于一个 $-a$ 操作之后同理.
那么就会有两种方案.
- 每次都使用 $+a$ 或 $-b$ 中可以执行的那一个执行.
- 每次都使用 $+b$ 或 $-a$ 中可以执行的那一个执行.
注意到都是由 $v$ 开始延伸的两条链.
结论 $2$ : 这两条链除了 $v$ 以外没有交点.
先证明一条链内没有公共点, 不妨以第一条链为例.
注意到其实每个状态是固定的, 因此重复即为出现循环, 同时最小的循环里面不会有重复的数.
任取循环中的一个点 $x$ , 设其下一次到 $x$ 总共走了 $p$ 次 $+a$ , $q$ 次 $-b$ , 那么有 $pa=qb$ .
而 $gcd(a,b) = 1$ , 因此有 $a|q$ 且 $b|p$ , 同时 $p,q \in \mathbb{Z}^+$ , 可以得到 $p+q \geqslant a+b \geqslant m+2$ , 根据抽屉原理, 必然有重复的数, 矛盾.
再证明两条链除了 $v$ 以外没有公共点.
不妨设这个公共点为 $x$ , 假设是从第一条链走到 $x$ 的, 那么总可以沿着第二条链的逆过程走回 $v$ , 根据唯一性, 这两条链其实就是一条链, 矛盾.
综上, 得证.
因此答案即为两条链长的和 $+1$ , 根据对称性不妨只考虑第一条链.
假设链中 $+a$ 的次数为 $p$ , 不难推出链长为 $p+\lfloor \frac{v+pa}{b} \rfloor$ , 因此就是要求出最小的 $p$ 使得, $(v+pa)mod \; b+a > m$ .
令 $v_0 = v \; mod \; b$ , 特判 $v_0+a > m$ 的情况, 这时 $p=0$ .
若 $v_0+a \leqslant m$ , 必然要有 $v_0+pa \; mod \; b < b$ , 进而原式为 $v_0+pa \; mod \; b+a < m$ .
原式等价于 $pa \; mod \; b \in [L,R]$ (其中 $L = m-a-v_0+1$ , $R = b-v_0-1$ ).
不妨设 $b = ka+r$ (其中 $0 \leqslant r < a$) 且 $qb \leqslant pa < (q+1)b$ , 那么限制即为,
其中 $L’,R’$ 为 $mod \; a$ 意义下的区间, 之后类欧几里德即可, 复杂度 $\mathcal{O}(t \log{m} )$ .