题意
在一个长度为 (n) 的序列中，找 (k) 个长度互不相同的区间互不重叠，求方案数。
Solution
经过简单的计算，发现普通的组合数并不能直接把方案数算出来，因为要考虑的情况实在太多了。那么我们可以考虑另一种能够算出方案数的方法——计数DP。
在上面的题意中，我将本题目的重点加粗了。那么我们可以设 (f_{i,j}) 表示 (i) 个不同的区间，总长度为 (j) 且区间长度递增的方案数（为什么要递增下面会说）。则状态转移方程为 (f_{0,0}=1,f_{i,j}=f_{i,,j-i}+f_{i-1,j-i}) ，指的是可以将原方案的 (i) 个区间都加上一，或者加上一再多一个长度为 (1) 的区间。
那么这个东西和答案有什么关系呢？
这里我们先把最后答案的式子写出来， (ans=k!sumlimits_{i=1}^ninom {n-i+k}kf_{k,i})
意思是枚举区间总长 (i) ，会出现 (n-i) 的空隙，那么就是在 (n-i) 的空隙和 (k) 个区间中选 (k) 个区间（或者像上面那份题解一样，将区间看成点），那么那个 (i) 就是要用到 (f) 的地方，但是因为是递增，所以要乘上 (A_k^k=k!) 代表全排列，此时答案为 (ans=sumlimits_{i=1}^ninom {n-i+k}kk!f_{k,i}) ，将 (k!) 提前，就是上面的式子了。
因为阶乘，组合数和 (f) 在运算过程中和 (n,k) 无关，所以可以提前预处理，直接查询。
小细节：因为如果选择区间长度为 (1,2,3cdots) ，可得 (dfrac {k(k+1)}2leq1000) ，解得 (kleq 45) ，所以可以特判一下（我特判的50）
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1010,mod=1e9+7;
int t,n,k;
ll fac[N],inv[N],f[60][N],ans[N][60];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
inline ll mul(ll a,ll b){return a*(ll)b%mod;}
inline ll add(ll a,ll b){return a+b>mod?a+b-mod:a+b;}
inline ll fpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
inline void init(){
fac[0]=1;
for(int i=1;i<=1000;i++) fac[i]=mul(fac[i-1],i);
inv[1000]=fpow(fac[1000],mod-2);
for(int i=1000;i>0;i--) inv[i-1]=mul(inv[i],i);
}
inline ll C(ll n,ll m){
if(n<m) return 0;
return mul(fac[n],mul(inv[n-m],inv[m]));
}
int main(){
init();
f[0][0]=1;
for(int i=1;i<=50;i++)
for(int j=i*(i+1)/2;j<=1000;j++)
f[i][j]=add(f[i][j-i],f[i-1][j-i]);
for(int i=1;i<=1000;i++)
for(int k=1;k<=50;k++){
for(int j=k*(k+1)/2;j<=i;j++){
ans[i][k]=add(ans[i][k],mul(C(i-j+k,k),f[k][j]));
}
ans[i][k]=mul(ans[i][k],fac[k]);
}
t=read();
while(t--){
n=read();k=read();
if(k>50) puts("0");
else printf("%lld
",ans[n][k]);
}
return 0;
}