记录编号	441968	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]组合数问题	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.543 s
提交时间	2017-08-25 21:40:32	内存使用	31.33 MiB

#include<cstdio>
#include<cctype>
#include<algorithm>
const int maxn=2017;
using namespace std;
inline int get();
int t,k;
int C[maxn][maxn],num[maxn][maxn];
int main()
{
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	t=get(),k=get();C[1][1]=1;
	for(int i=1;i<=2000;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(j==1)C[i][j]=i%k;
			else if(j==i)C[i][j]=1%k;
			else C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;
			if(C[i][j])
			{
				if(j==1)num[i][j]=num[i-1][j];
				else if(i==j)num[i][j]=num[i][j-1];
				else num[i][j]=num[i][j-1]+num[i-1][j]-num[i-1][j-1];
			}
			else
			{
				if(j==1)num[i][j]=num[i-1][j]+1;
				else if(i==j)num[i][j]=num[i][j-1]+1;
				else num[i][j]=num[i][j-1]+num[i-1][j]-num[i-1][j-1]+1;
			}
		}
	}
	while(t--)
	{
		register int n=get(),m=get();
		printf("%d\n",num[n][min(n,m)]);
	}
	return 0;
}
inline int get()
{
	int t=0,j=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')j=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return j*t;
}