题解：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 才有解因此是对的。

submission