题目理解

有 $n$ 支队伍参加 ICPC 竞赛，封榜前第 $i$ 支队伍的过题数为 $a_i$。

滚榜时，主办方按照 $b_i$ 不降 的顺序依次公布每支队伍的封榜后过题数 $b_i$，且每次公布后该队伍都会成为当前排行榜的第一名。

已知所有队伍封榜后总过题数 $\sum_{i=1}^n b_i = m$，求最终排行榜上队伍排名情况的可能数。

---

关键观察

1. 排名规则

• 按总过题数 $a_i + b_i$ 从大到小排序
• 题数相同时，编号小的队伍排名靠前

2. 公布顺序的限制

• $b_i$ 序列必须非递减
• 每次公布后，当前队伍必须成为第一名

3. 问题转化

这实际上是一个状压 DP 计数问题：

• 状态表示哪些队伍已经公布了 $b_i$
• 需要保证每次新公布的队伍能超过当前第一名

---

算法思路

状态设计

设 $f[S][i][j]$ 表示：

• $S$：已公布队伍的集合（状态压缩）
• $i$：当前最后公布的队伍编号
• $j$：已使用的 $b_i$ 总和

值为达到该状态的方案数。

状态转移

从状态 $f[S][i][j]$ 出发，枚举下一个公布的队伍 $k$（$k \notin S$）：

队伍 $k$ 要成为新的第一名，其 $b_k$ 必须满足：

1. $b_k \ge b_i$（$b$ 序列非递减）
2. $a_k + b_k \ge a_i + b_i$（成为第一名）

实际上可以计算出 $b_k$ 的最小值：

$$b_k = \max(b_i, a_i + b_i - a_k + [k > i])$$

其中 $[k > i]$ 是处理编号比较的细节：当题数相同时，编号小的排名靠前。

初始状态

对于每个队伍 $i$，如果它能成为第一个公布的队伍：

$$f[2^{i-1}][i][n \times g(id, i)] = 1$$

其中 $id$ 是封榜前过题数最多的队伍编号，$g(x,y)$ 是计算 $y$ 要超过 $x$ 所需的最小 $b_y$。

最终答案

$$\text{ans} = \sum_{i=1}^n \sum_{j=0}^m f[2^n-1][i][j] $$

---

复杂度分析

• 状态数：$O(2^n \cdot n \cdot m)$
• 转移复杂度：$O(n)$
• 总复杂度：$O(2^n \cdot n^2 \cdot m)$

对于 $n \leq 13$，$m \leq 500$，该算法可以通过。

---

算法标签

• 状态压缩动态规划
• 计数问题
• 排列计数

---

总结

本题通过状态压缩 DP 巧妙地处理了滚榜过程中的各种约束条件：

1. $b_i$ 的非递减性
2. 每次公布后当前队伍成为第一名
3. 总 $b_i$ 和为 $m$

算法充分利用了 $n$ 较小的特点，通过状压枚举所有可能的公布顺序，是经典的计数类 DP 问题。