CF2171(div. 3) VP & 补题笔记

E

Statement

对于一个数组 $a$ ，当且仅当 $\gcd(a_i, a_{i+1}) = \gcd(a_i, a_{i+2}) = \gcd(a_{i+1}, a_{i+2}) = 1$ 时， $i$ 为一个好索引，反之则为坏索引。给定 $n \le 2 \times 10^5$ ，构造排列 $a_n$ 使得其中坏索引数量不超过 $6$。

Solution

将具有相同因子的数构造成 XX_XX_XX_XX... 的形状较优，将偶数与 $3$ 的奇数倍数分别构造成这种形状可以满足题意。
submission

G

Statement

给定两个长度为 $n \le 2 \times 10^5$ 的数组 $a$ 和 $b$ ，两种操作分别为：

• 选择 $i$ 使得 $a_i := a_i+1$ 。
• 对于所有的 $i$ 使得 $a_i := a_i \times 2$ 。

求使得 $a=b$ ,最小的操作次数\使得操作次数最小的操作序列数量（ 对 $10^6+3$ ）取模。

Solution

尽量多使用操作 $2$ 显然更优，因此 操作 $2$ 的数量唯一确定。

如果某一个操作 $1$ 之后有 $x$ 个操作 $2$，相当于给 $a$ 加上 $2^x$ 。

因此也可以唯一确定操作 $1$ 的数量。只有若干个操作 $2$ 之间（包括第一个操作 $2$ 和最后一个操作 $2$ 之后），一组操作 $1$ 的顺序可以调换。

根据组合数学原理，对于每一组操作 $1$，方案数为 $\frac{(\sum{p})!}{\prod{(p_i!)}}$ ， 其中 $p_i$ 为第 $i$ 个数的操作 $1$ 的数量。

注意代码实现的时候， $(\sum{p})!$ 可能会超过 $\text{mod}$ ，此时答案即为 $0$ ，因为分子一定含有因子 $\text{mod}$，而分母一定不含有因子 $\text{mod}$，即 $\frac{(\sum{p})!}{\prod{(p_i!)}} \mod (10^6+3) = 0$ 。

submission

H

Statement

给定两个整数 $n$ 和 $m$ （ $2\leq n\leq m \leq 2\cdot 10^5$ ），最大化严格单调递增数组 $a_n$ 的 $\Sigma_{i=2}^{n}v(i,a_i)$ 的取值，其中 $v(b, x)$ 为最大的 $k$ 使得 $b^k \mid x$。

Solution

考虑 dp，令 $dp_{i,j}$ 为 $a_i$ 已确定为 $j+i$ 时最大的 $\Sigma v$ ，这样 $dp_{i,j}$ 可以由任意 $dp_{i,j'}(j'<=j)$ 转移过来，且 $\Sigma v$ 的增加量只与 $j$ 有关而与 $j'$ 无关，故可以使用滚动数组，并用树状数组维护区间最大值。

submission