题解：CF403D Beautiful Pairs of Numbers
_ckx_
·
·
题解
CF Duel 到的，极限拿下了。
题目大意
有 t 个询问，每个询问给定 n，k，求满足以下条件的长度为 k 的二元组序列个数：
-
- 所有数 b_{1}-a_{1} ， b_{2}-a_{2} ，\ldots， b_{k}-a_{k} 两两不同。
分析
首先 b 与 a 的差两两不同，且 a、b 都不降，说明 a、b 增长很快，k 太大时答案都是 0，构造一下，最坏情况下是 (1,1),(2,4),(5,8),(9,13)... 算一下 k 大于 50 答案就肯定是 0。
此时可以 O(n^2k) 了，尽量往上靠。
然后可以把 (a_i,b_i) 看成一个区间 [a_i,b_i]，此时我们只需要知道区间总长度 s，那么这个总长度贡献的答案就是 \frac{(k+n-s)!}{(n-s)!}（每个区间的左端点 和 不在任何区间里的点 的任意一种排列方法都对应一种方案，除掉的是 不在任何区间里的点 的内部顺序）。
此时就很像 DP 了，先确定两个状态：目前加入了几个区间、此时区间总长度。
现在考虑第二个限制，转化后就是区间长度两两不同，这个两两不同十分不好处理，所以我们可以考虑按长度从小到大加入区间，并保证每种长度之加入一次。
此时状态就完全出来了：
转移：
$f_{i,j,k}=f_{i,j-1,k}+f_{i-1,j-1,k-j}$：分别对应加入/不加入长度为 $j$ 的区间。
最后统计答案时枚举最终区间总长度并用刚刚那个式子贡献就行了。
## 注意
开不下 $O(50n^2)$ 的数组，开太小又会 RE，所以要把询问离线下来，对 $k$ 作扫描线（也就是把 $k$ 相等的统一处理）。
## code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
ll ret = 0 ,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') f = (ch == '-' ? -f : f) ,ch = getchar();
while (ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0' ,ch = getchar();
return ret * f;
}
const int mod = 1e9 + 7;
const int N = 1010 ,K = 50 ,T = 2e5 + 10;
ll f[2][N][N]; //滚动优化空间
ll fac[N] ,inv[N] ,ans[T];
struct Q{
int n ,id;
};
vector<Q> que[K];
ll qpow(ll a ,ll b)
{
ll ret = 1;
while (b)
{
if (b & 1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}
int main()
{
fac[0] = inv[0] = 1;
for (int i = 1;i < N;i++) fac[i] = fac[i - 1] * i % mod;
inv[N - 1] = qpow(fac[N - 1] ,mod - 2);
for (int i = N - 2;i >= 1;i--) inv[i] = inv[i + 1] * (i + 1) % mod; //预处理阶乘及其逆元
int t = read();
for (int i = 1;i <= t;i++)
{
int n = read() ,k = read();
ll now = 0;
bool f = false;
for (int j = 0;j < k;j++)
{
now++ ,now += j;
if (now > n) { ans[i] = 0; f = true; break; } //判答案为 0
}
if (!f) que[k].push_back({n ,i}); //把答案不为0的询问离线下来
}
for (int i = 0;i < N;i++) f[0][i][0] = 1;
for (int i = 1 ,nw = 1;i < K;i++ ,nw ^= 1)
{
memset(f[nw] ,0 ,sizeof(f[nw]));
for (int j = 1;j < N;j++)
for (int k = 0;k < N;k++)
{
f[nw][j][k] = f[nw][j - 1][k];
if (k >= j) f[nw][j][k] = (f[nw][j][k] + f[nw ^ 1][j - 1][k - j]) % mod; //转移
}
for (auto q : que[i])
{
int id = q.id ,n = q.n;
for (int j = 1;j <= n;j++)
ans[id] = (ans[id] + f[nw][n][j] * fac[i + n - j] % mod * inv[n - j] % mod) % mod; //贡献答案
}
}
for (int i = 1;i <= t;i++) printf("%lld\n",ans[i]);
return 0;
}
```