too difficult for 蒟蒻
题意
已知有 $n \le 13$ 个数 $a_i \le 10^4$ ，按 $1 \sim n$ 编号，每次选一个数给他加上 $b_i$ ，要保证加的 $b_i$ 不小于上次加的，且加完后该数排名第一（大小相同的比编号），已知 $\sum b_i = m \le 500$ ，求最后 $n$ 个数的排名情况有多少种
做题
看 $n \le 13$ 考虑状态压缩，设 d[s][i][j][k] 表示“已加的数集合为 $s$ ，上一个加的为 $i$ ，当前 $\sum b_i = j$ 且上一个 $b_i = k$ 的方案数”，有 $d[s][i][j][k] \to d[s + \{p\}][p][j + q][q]$ （满足 $a_p + q > / \ge a_i + b_i, j + q < m, q \ge k$ ）时间复杂度为 $O(2^n n^2 m^2)$ 呃呃……
考虑把状态的维度剪掉，当然是剪一个 $m$ （剪 $n$ 没用啊），发现我们不必要上一个 $b_i$ ，考虑用别的前几维的信息得到 $b_i$ ，发现不是很好表示
考虑预处理，首先，我们发现数 $a_i$ 要变成最大的， $b_i$ 就要比 $b_j$ 大至少 $a_j - a_i$ （假设 $j$ 先于 $i$ ），不妨设它为 $dt[i][j]$ ，计算它要用 $O(n^2)$
其次，由于 $b$ 按出现的顺序单调不降，不妨考虑差分，设差分数组为 $c$ ，有 $b_i = \sum_{j = 1}^i c_i$ （这里假设 $b_i$ 按出现顺序排序了， $b_i$ 的 $i$ 已经不对应 $a_i$ 了），故 $\sum b_i = \sum c_i * (n - i + 1) = m$ ，所以 $c_i$ 对 $m$ 的贡献就要乘 $n - i + 1$ ，只需保证 $c_i \ge 0$ 即可，而 $c_i$ 的最小值就是 $dt[i][j]$ （ $j$ 先于 $i$ 一个）
再次定义 d[s][i][j] 为“已加的数集合为 $s$ ，上一个加的为 $i$ ，当前 $\sum b_i = j$ 的方案数”，设 $t = s - \{i\}$ ，有 $d[s][i][j] \gets d[t][k][j - dt[i][k] * (n - \mid A \mid)]$ ，时间为 $O(2^n n m)$ ，常数小可过
代码
1 |
|