\(\text{luogu-7419}\)
封榜是 ICPC 系列竞赛中的一个特色机制。ICPC 竞赛是实时反馈提交结果的程序设计竞赛，参赛选手与场外观众可以通过排行榜实时查看每个参赛队伍的过题数与排名。竞赛的最后一小时会进行“封榜”，即排行榜上将隐藏最后一小时内的提交的结果。赛后通过滚榜环节将最后一小时的结果（即每只队伍最后一小时的过题数）公布。
Alice 围观了一场 ICPC 竞赛的滚榜环节。本次竞赛共有 \(n\) 支队伍参赛，队伍从 \(1 \sim n\) 编号，\(i\) 号队伍在封榜前通过的题数为 \(a_i\)。排行榜上队伍按照过题数从大到小进行排名，若两支队伍过题数相同，则编号小的队伍排名靠前。
滚榜时主办方以 \(b_i\) 不降的顺序依次公布了每支队伍在封榜后的过题数 \(b_i\)（最终该队伍总过题数为 \(a_i + b_i\)），并且每公布一支队伍的结果，排行榜上就会实时更新排名。Alice 并不记得队伍被公布的顺序，也不记得最终排行榜上的排名情况，只记得每次公布后，本次被公布结果的队伍都成为了新排行榜上的第一名，以及所有队伍在封榜后一共通过了 \(m\) 道题（即 \(\sum_{i = 1}^{n} b_i = m\)）。
现在 Alice 想请你帮她算算，最终排行榜上队伍的排名情况可能有多少种。
\(1 \le n \le 13\)，\(1 \le m \le 500\)，\(0 \le a_i \le {10}^4\)。
以下部分题解来自于 P7519 省选联考 2021 A/B 卷 滚榜 题解 - 洛谷专栏。
考虑到数据范围很小，\(n \leq 13\)，不难想到状压 dp。
进行状态设计。既然是状压不可能没有 \(O(2^n)\) 一维。
因为我们 \(b_i\) 的决定会和上一个人有关，显然储存上一个人是谁这一维无可避免，\(O(n)\)。
剩下的一个比较好想的做法是，保存上一个人的 \(b_i\) 是多少，已经当前已经多用了多少题。这样有两个 \(O(m)\) 级别的信息。
暴力即为暴力转移，时间复杂度 \(O(2^nn^2m^2)\) 或者 \(O(2^nnm^2)\)，空间复杂度 \(O(2^nnm^2)\)。
注意到我们统计的是排名的方案数，跟具体的 \(b_i\) 是无关的，也就是说，保存上一个人的 \(b_i\) 是无效信息。
考虑将这一维删去，也就是说我们需要通过一些操作使得这一维的信息能够被表示或者忽略。
被表示估计不太行。注意到 \(b\) 序列单调不降，考虑差分，将新数列记为 \(\Delta\)。因为 \(b\) 序列单调不降，所以 \(\forall i \in [1,n],\Delta_i \geq 0\)。
注意到 \(\Delta_i\) 会使得所有 \(j \geq i\) 的 \(b_j\) 增加 \(\Delta_i\)。考虑每次加入 \(\Delta_i\) 的时候把后面的影响一并处理。
具体想法是，我们将 \(i\) 滚榜的时候，不用知道上一个的 \(b\) 到底是多少也能满足 \(b\) 不降。那么我们每次在处理的时候每次加入 \(\Delta_i\)，后面的所有 \(b\) 也同时加上 \(\Delta_i\)。这样我们就相当于枚举差分值，显然是可以满足 \(b\) 单调不降的条件的。只需要考虑单纯的，不考虑 \(b_i\) 的从 \(u\) 转移到 \(v\) 的最少的题数了。
也许这个东西叫做费用提前计算？
考虑实现，预处理一个数组 \(c_{i,j}\) 表示上一个是 \(i\)，这次滚榜到 \(j\) 需要的最小的 \(b_i\)。至于不用考虑上一个 \(i\) 加上的 \(b_i\) 的原因因为我们在上面的做法中规避了这个问题，不理解还可以返回去看。代码写起来就很简单了。
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
#define MAXN 14
#define MAXM 505ll read() {ll x = 0, f = 1;char c = getchar();while(c < 48 || c > 57) { if(c == 45) f = -1; c = getchar(); }while(c >= 48 && c <= 57) { x = (x << 3) + (x << 1) + (c - 48); c = getchar(); }return x * f;
}ll n, m, a[MAXN], w[MAXN][MAXN], dp[1 << MAXN][MAXN][MAXM];ll lowbit(ll x) { return x & (-x); }ll popc(ll x) { ll res = 0; while(x) x -= lowbit(x), res ++; return res; }int main() {n = read(), m = read();for(int i = 1; i <= n; i ++) a[i] = read();for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++)w[i][j] = max(0ll, a[i] - a[j] + (i < j)), w[0][j] = max(w[0][j], w[i][j]);dp[0][0][0] = 1;for(int S = 0; S < (1 << n); S ++) if(S == lowbit(S)) {ll res = 0;for(int i = 1; i <= n; i ++) if((S >> (i - 1)) & 1 && (res = i)) break;if(n * w[0][res] <= m) dp[S][res][n * w[0][res]] = 1;}else for(int i = 1; i <= n; i ++) if((S >> (i - 1)) & 1) {ll T = S ^ (1 << (i - 1)), y = i;for(int j = 1; j <= n; j ++) if((T >> (j - 1)) & 1) {ll x = j, p = n - popc(T);for(int k = w[x][y] * p; k <= m; k ++)dp[S][y][k] += dp[T][x][k - w[x][y] * p];}}ll res = 0;for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) res += dp[(1 << n) - 1][i][j];cout << res << "\n";return 0;
}