比赛链接

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)$ 次操作就能分解完毕。

Upsolved by nikkukun.

剧场中有 $n \times m$ 个座位，有 $k$ 对双人组前来看剧，组中的两个人应当认为是不同的人。如果双人组相邻地坐着，他们会因为争吵影响别人看剧。现在已知一些位置不能坐，求让这 $2k$ 个人能好好看剧的方案数模 $10^9 + 7$。

$n \times m \in [1, 144]$，保证有不少于 $2k$ 个空位置。

容斥。令 $f(i)$ 表示取 $i$ 对双人组相邻地坐着的方案数，则答案为

$$ 2^k \cdot \left[ \sum _{i=0}^k (-1)^i \cdot \binom ki \cdot i! \cdot f(i) \cdot \binom {\mathrm{res} - 2i}{2k-2i} \cdot \frac {(2k-2i)!}{2^{k-i}} \right] $$

其中 $\mathrm{res}$ 为可以坐的座位。

现在考虑如何求 $f(i)$，不妨假设 $m \leq n$（不满足时转置一下），则相当于在有禁位的棋盘上放 $i$ 个骨牌，可以类似插头 DP 一样用一个二进制保存 $m + 1$ 个位置的跨越状态。

在某一行上，令 $g(\mathrm{pos},\mathrm{cnt}, \mathrm{sta})$ 表示当前处理到的列为 $\mathrm{pos}$、放置了 $\mathrm{cnt}$ 个骨牌、插头状态为 $\mathrm{sta}$，则处理到最后一行时有 $f(i) = g(m, i, 0)$。注意要用滚动数组，减少空间开销。

单次时间复杂度 $O(nmk \cdot 2^{\min\{n, m\}})$。

Solved by nikkukun.

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

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