比赛链接

Solved by qxforever.

给 $n \leq 10^6$ 个值域在 $[1, 10^6]$ 的数 $a_1, a_2, \ldots, a_n$，求有多少对二元组 $(i, j)$ 满足 $\binom {a_i}{a_j}$ 是奇数。

由 Lucas 定理可知

$$ \binom mk \equiv \binom {m/2}{k/2} \binom {m \bmod 2}{{k \bmod 2}} \pmod 2 $$

式子为 $1$，当且仅当不存在某个二进制位上 $m = 0$ 而 $k = 1$，即 $m \land k = k$，因此需要求对每个 $a_i$ 有多少个 $a_j$ 是它的子集，这用 SOS DP 可以计算得到。

总时间复杂度 $O(\max \{a_i\} \log \max \{a_i\})$。

Solved by Potassium & nikkukun.

给一个不超过 $10^5$ 位的十进制数，拆成不超过 $25$ 个回文正数（不含前导零）的和。

例如 $2020 = 2002 + 11 + 7$。

每次取 $n$ 的前 $\left\lceil \dfrac n2 \right\rceil$ 位 $a$ 出来，并反过来接在后面变成 $aa^r$ 作为本次减的数。如果 $n < aa^r$，则将 $a$ 减去 $1$ 变为 $b$ 后，以 $bb^r$ 作为本次减的数。

观察发现这样操作每次会减少一半的位数，只要 $O(\log \log n)$ 次操作就能分解完毕。

Solved by nikkukun.

有 $n$ 个箱子，每个箱子用金钥匙或银钥匙都可以开，开启时间为 $t_i$。金钥匙只有一个，不能同时开几个箱子；银钥匙有 $k$ 个，可以同时开多个箱子。求打开所有箱子的最短时间。

排序后贪心用金钥匙开时间最小的 $n-k$ 个箱子即可。