比赛链接

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\})$。

Upsolved by nikkukun.

给 $n \leq 2 \times 10^5$ 个数 $x_1, x_2, \ldots, x_n$（$x_i \in [0, 3 \times 10^{11}]$）和一个参数 $d \in [1, 10^6]$，你可以将这个序列的值任意改动为其余非负整数，使得对任意的 $i \neq j$ 都有 $|x_i - x_j| \geq d$，代价为每个数的改变量绝对值之和。

求最小代价。

不妨考虑先将 $x$ 数组排序，并在维持相对位置的情况下，使得排序后数组 $x_{i+1} - x_i \geq d$，这样原题的条件便得到满足。

先转化条件为非降序列：要求 $x_{i+1} - x_i \geq d$，则令 $x'_i = x_i - (i - 1) \cdot d$，就变成了令 $x'_{i+1} \geq x_i'$ 的条件。

再保证所有数非负：对所有 $x_i' < 0$ 的数，都将其先改为 $0$，并将变化量统计在答案中。此时显然转化回 $x_i$ 的数组既非负，又满足了条件。同时，在 $x_i'$ 中由于所有数也非负，为了用最小代价将 $x_i'$ 变为非降，不会把某些 $x_i'$ 重新调回负数，这并不优。

于是，现在问题变成让 $x'$ 数组非降，而这是经典 $L_1$ 问题，参考 保序回归问题。

Solved by Potassium.

$n$ 个互相无交点的圆是原子弹伤害范围，有 $q$ 次查询，每次查两个位于 $x_1$ 和 $x_2$ 坐标，且 $y$ 坐标可以任意游走于 $[ymin,ymax]$ 的动物能否相遇。

有显然结论：如果两动物不能相遇，一定有一个圆跨过 $[ymin,ymax]$ 且位于两点之间。于是将圆和动物都放在 $ymin$ ，从小到大枚举，遇到动物就查询中间能够到达的最大 $y$ 值，如果超过 $ymax$ 则无法到达；遇到圆就更新 $c_x$ 处的值为 $c_y+r$。

Upsolved by qxforever.

给一个长度 $n$ 的排列，三种操作（交换相邻数字，反转序列，随机排列序列）分别对应花费为 $a$ , $b$ , $c$ ，要还原成元排列（$p_i=i$），问期望花费。对每组 $(n,a,b,c)$ 要回答 $d$ 次询问。 $n\le16$，$\sum d\le10^5$

当不考虑第三种操作时，每个排列的花费是一定的，且只和这个排列的逆序对数 $inv$ 有关，为 $\min(inv\times a,(n(n-1)/2-inv)\times b )$。通过一个 $O(n^32^n)$ 的 DP 预处理出长度为 $n$ 的排列中逆序对为 $inv$ 的方案数，记为 $num_{inv}$ 。

现在考虑第三种操作，若当前排列对应的花费较高，我们应该考虑随机这个排列直到它的花费满足要求。因此首先将 $(cost_i,num_i)$ 按照第一维排序。设随机排列花费的期望为 $E$，则有 $$ E\times n!=(E+c)\times \sum_{i>j}num_i + \sum_{i\le j} num_i\times cost_i $$ 式子的含义是，若当前排列的花费大于 $cost_j$ 进行随机，否则取当前排列的花费为最终花费。 $E$ 的值与 $j$ 有关，遍历 $j$ 维护 $E$ 的最小值即可。

问题的答案为 $\min(cost_{inv},E+c)$ 。

Solved by Potassium.

签到构造题，跳了

Solved by Potassium.

给一个凸多边形以及一些顶点间的路，求最长不重复经过点的路径。

区间 $dp$，考虑某个区间不能选和终点位置，向外转移即可。

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$ 个箱子即可。