testB
输入文件: testB.in 输出文件testB.out 时限3000ms
问题描述：
定义这样一个序列(a1,b1),(a2,b2),…,(ak,bk)如果这个序列是方序列的话必须满足下面两个条件：
(1)1<=a1<=b1<a2<=b2<….<ak<=bk<=n 。其中n是给定的正整数。
(2)b1-a1,b2-a2,….,bk-ak两两互不相同。
现在方老师想知道给定n的情况下有多少种不同的长度为k的方序列。
答案取模10^9+7
输入描述：
第一行一个数t表示有t组测试数据。(t<=2*10^5)
第二行至第t+1行每行两个数n和k。(1<=k<=1000 , 1<=n<=1000)
输出描述：
一共t行，每一行表示一个答案。
样例输入：
6
1 1
2 1
2 2
3 1
3 2
3 3
样例输出：
1
3
0
6
2
0
经过观察，k不可能大于50,将（a[i],b[i]）看做一个区间，原题转化为选k各不同的正整数，使其总和<=n。
dp[i][j]表示选到第i个数，和为j的方案个数。对于dp中每一种合法方案，通过组合数算出答案。
这道题难点在于多次dp的使用，越界的处理等
总结一点经验：当在较大数据下，你的答案与标答有个位数的差别时，有以下两种可能：1、数组小范围越界，2、你将1000000007打成了1000000009
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define PROB "testB"
#ifdef unix
#define LL "%lld"
#else
#define LL "%I64d"
#endif
#define MAXN 1002
#define VAL1 1000000007
//define deal(x,y) x+=y;if (x>=VAL1)x%=VAL1;
typedef unsigned long long qword;
qword dp[MAXN+][];//x表示区间和，y表示个数，dp表示区间长度组合数，已省略第一维
qword dp2[MAXN+][];//x表示总和，y表示个数，dp表示答案
qword fact[MAXN+];
qword c[MAXN+][MAXN+];
int n;
inline void deal(qword &x,qword y)
{
x+=y;
if (x>=VAL1)x%=VAL1;
}
void init()
{
int i,j,k;
//cout<<"a1"<<endl;
fact[]=;
for (i=;i<=MAXN;i++)fact[i]=(fact[i-]*i)%VAL1;
c[][]=;
for (i=;i<=MAXN;i++)
{
for (j=;j<=i;j++)
{
c[i][j]=(((j)?c[i-][j-]:)+c[i-][j])%VAL1;
}
}
dp[][]=dp[][]=;
//cout<<"a2"<<endl;
for (k=;k<=MAXN;k++)
{
for (i=MAXN-;i>=;i--)
{
for (j=;j>=;j--)
{
if (dp[i][j]&&i+k<=MAXN)
{
deal(dp[i+k][j+],dp[i][j]);
}
}
}
}
//cout<<"a3"<<endl;
for (i=;i<=MAXN;i++)
{
for (j=;j<=;j++)
{
dp2[i][j]=;
for (k=;k<=i-j;k++)
{
if (j++i-j-k->=i-j-k)
deal(dp2[i][j],dp[k][j]*fact[j]%VAL1*c[(j+)+(i-j-k)-][i-j-k]%VAL1);
}
}
}
}
int main()
{
//freopen(PROB".in","r",stdin);
//freopen(PROB".out","w",stdout);
init();
qword ans;
int m,x,y;
scanf("%d",&m);
while (m--)
{
scanf("%d%d",&x,&y);
if (y>)printf("0\n");else printf(LL"\n",dp2[x][y]);
}
}