题解：CF403D Beautiful Pairs of Numbers

*2300 的 组合计数。

两个条件：

肯定要预处理所有 $(n,k)$ 组合的答案，因为 $t$ 很大，但 $n,k$ 较小。

先尝试求出有解的充要条件。根据条件 1 可知，相邻一对至少会增加 $1$，有 $k-1$ 次增加，因此有 $b_k-a_1=(\sum\limits_{i=1}^k b_i-a_i)+k-1 \le n-1$，解得 $(\sum\limits_{i=1}^k b_i-a_i) \le n-k$。

根据条件 2，有下界 $\sum\limits_{i=1}^k b_i-a_i \ge \sum\limits_{i=1}^k i-1=\dfrac{k \times (k-1)}{2}$。

由两个不等式有 $\dfrac{k \times (k-1)}{2} \le n-k$，因此 $k^2+k \le 2 \times n$。所以 $k$ 很大是没有用的，因此只考虑 $k \le 50$ 即可，否则无解。

再来考虑 dp，对于一组询问 $(n,k)$ 怎么算答案。对于条件 2 的 $k$ 个数对，差值可以选择 $0 \sim n$，我们要固定选择 $k$ 个数。

然后你在上述有解分析的时候大概想到了如果 $b_k-a_1 \le n-1$，那你相当于还会剩下 $n-(b_k-a_1)-1$ 次多余的“操作”可以加到 $a_i$ 里去。就是说对于 $a_1 \sim a_k$，你最多还可以把 $n-(b_k-a_1)-1$ 分配给他们。然后 $b_i$ 会对应的增加，是随着 $a_i$ 变化的，因此不需要管 $b_i$。

但是这个 $b_k-a_1$ 对于不同的在 $n$ 个差值里选择 $k$ 个的方案的情况下也是不同的。因此我们考虑枚举与这个相关的东西。

我们枚举选出的 $k$ 个数的和为 $j$，其方案数记为 $f_{j,k}$，那么可以算出你最多可以分配的量为 $(n-1)-j-(k-1)=n-j-k$。具体细节后面再讲。

然后你选出的 $k$ 个差值是可以任意调换的，因此要乘上 $k!$。然后枚举 $p \in [0,n-j-k]$ 表示你要分配 $p$ 个数给 $k$ 个 $a_i$。这个问题是经典的插板法，方案数为 $\dbinom{p+k-1}{k-1}$，这里不再赘述。因此这部分方案数为 $\sum\limits_{p=0}^{n-j-k} \dbinom{p+k-1}{k-1}$。这个东西不要暴力求，可以预处理。

然后求 $f$ 数组的话相当于是做一个背包，我们枚举 $i$ 表示当前的 $n$，然后每次都 $O(nk)$ 做一次 01 背包。对于 $n=i$ 时统计答案，枚举 $k$，则 $ans_{n=i,k}=\sum\limits_{j}^{n-1} f_{j,k} \times k! \times \sum\limits_{p=0}^{n-j-k} \dbinom{p+k-1}{k-1}$ 。

预处理后复杂度是 $O(n^2k)$ 的，因为 $k \le 50$ 才有解因此是对的。