CF2119 VP&补题笔记

D

Statement

合法序列 $a$ 满足 $0 \le a_i \le i$。
$f(a)$ 的定义为：初始有 $n$ 个标记，依次从 $[a_i,i]$ 上移除一个标记（ $a_i=0$ 则不做操作），$f(a)$ 即为移除标记排列数。

给定 $n \leq 5000$，对于所有长度为 $n$ 的合法序列 $a$，求 $\sum{f(a)}$ 。答案对 $m$ 取模。

Solution

正难则反，考虑对每一种标记移除排列方案，从后往前考虑每一个被移除的标记 $i$ ，设已经被移除的标记数为 $j$，其可能的被移除的方式有 $i \times (n-i+1-j)$ 种。对于整个排列方案，运用乘法原理即可。

令 dp[i][j] 为到位置 $i$ 的标记，已经移除了 $j$ 个标记的答案数，从后往前 dp 即可。
submission

E

Statement

给定一个长度为 $n-1$ 的序列 $a$ 和一个长度为 $n$ 的序列 $b$。要求增加 $b_i$ 的值（可以不变）使得 b_i & b_{i+1} = a_i 并使得 $b_i$ 的总增加量最小，求这个最小值。 $n \le 10^5 , a_i,b_i < 2^{29}$ 。

solution

首先 $b_i$ 一定是 $c_i = a_{i-1} | a_{i}$ 的超集，只需要在 $c_i$ 的基础上加位保证大于等于 $b_i$ 且满足约束条件即可。

对于每一个 $c_i$ ，从高到低位扫描，若是 $1$ 就跳过（不能做改动），若是 $0$ 就考虑变 $1$ ，如果变之后大于等于 $b_i$ 就将这个数加入候选列表里然后继续往下一位扫描，如果仍然小于就将这一位 $1$ 固定下来（这一位若不为 $1$，如何改动后面的低位也无法让这个数大于 $b_i$ 了）然后继续往后扫描，不难看出这一流程之后每个 $i$ 可取的数的数量不会超过 $32$ ，然后dp即可。
submission