Description：

一个正整数对序列 $(a_1, b_1),(a_2, b_2),\dots,(a_k,b_k)$ 是美观的当且仅当满足：

• $1\leqslant a_1\leqslant b_1<a_2\leqslant b_2<\dots <a_k\leqslant b_k\leqslant n$ 。

• $b_1-a_1,b_2-a_2,\dots,b_k-a_k$ 两两不同。

给出 $n$ 和 $k$ ，求出美观序列的个数。

$1\leqslant testcases\leqslant2\times 10^5,1\leqslant n,k\leqslant 10^3$

Solution：

首先抽象一下问题，就是在数轴上 $[1,n]$ 放很多不相交的线段，所有线段长度不同，问有多少种方法，首先可以注意到线段的总个数不会超过 $50$ ，因为 $1+2+4+\cdots+50>1000$ ，那也就是说可以承受比 $O(nk)$ 复杂度更高的做法，不妨假设线段长度是递增的，那么我们设 $DP$ 状态为 $f[i][j][k]$ 表示已经放了 $i$ 个线段，总长度为 $j$ ，最长的线段长度小于 $k$ 的方案数，初值为 $f[0][0][1]=1$ ，转移为 $f[i+1][j+k][k+1]+=f[i][j][k]$ ，注意每次要把 $f[i][j][]$ 做个前缀和，复杂度为 $O(\sqrt N\times N\times N)$ ，然后求答案的时候先把 $f[i][j][k]$ 乘上 $i!$ ，然后要把一些空位插到线段之间，我们现在有 $i+1$ 个间隔和 $n-j$ 个空位，按照组合数学中的做法可以得到答案为 $i+n-j\choose n-j$ ，乘起来求和就是答案。

发现有一个更好理解的做法， $f[i][j][k]$ 本质是一个两两不同的整数划分数，直接用 $g[i][j]=g[i][j-i]+g[i-1][j-i]$ 求解即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 1001

#define MOD 1000000007

void updata(int &x,int y){x = (x + y) % MOD;return;}

int g[51][MAXN];

int fac[MAXN];

#define MAX 2001

int C[MAX][MAX];

int ans[MAXN][MAXN];

int main()

{

	g[0][0] = 1;

	for(int i = 1;i <= 50;++i)

		for(int j = i;j < MAXN;++j)

			updata(g[i][j],g[i][j - i] + g[i - 1][j - i]);

	fac[0] = 1;

	for(int i = 1;i < MAXN;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

	for(int i = 1;i <= 50;++i)

		for(int j = 0;j < MAXN;++j)

			g[i][j] = 1ll * g[i][j] * fac[i] % MOD;

	C[0][0] = 1;

	for(int i = 1;i < MAX;++i)

	{

		C[i][0] = C[i][i] = 1;

		for(int j = 1;j < i;++j)

			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;

	}

	memset(ans,0,sizeof(ans));

	for(int n_ = 1;n_ < MAXN;++n_)

		for(int i = 1;i * (i + 1) / 2 <= n_;++i)

			for(int j = 1;j <= n_;++j)

				updata(ans[n_][i],1ll * g[i][j] * C[i + n_ - j][n_ - j] % MOD);

	int testcases;

	scanf("%d",&testcases);

	int n,k;

	while(testcases--)

	{

		scanf("%d%d",&n,&k);

		if(n == 1 && k == 1)puts("1");

		else printf("%d\n",ans[n][k]);

	}

	return 0;

}