记录编号	473094	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]组合数问题	最终得分	100
用户昵称	snake	是否通过	通过
代码语言	C++	运行时间	0.357 s
提交时间	2017-11-08 13:04:49	内存使用	31.22 MiB

//组合数问题
//#include<iostream>
#include<fstream>
#include<climits>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
using namespace std;
ifstream cin("problem.in");ofstream cout("problem.out");

const int MAX=2010;
int yh[MAX][MAX];
int s[MAX][MAX];	//前缀和
int question[2][5*MAX];

void build(int n,int k)	//打表 
{
	bool flag=!(1%k);
	for(int i=0;i<=n;i++) for(int j=0;j<=i;j++)
	{
		if(j==0) yh[i][j]=1;
		else yh[i][j]=(yh[i-1][j]+yh[i-1][j-1])%k;
		yh[i][j]%=k;
		if(i==0 && j==0)
		{
			if(flag) s[i][j]=1;
			else s[i][j]=0;
		}else if(j==0){
			if(flag) s[i][j]=s[i-1][j]+1;
			else s[i][j]=0;
		}else if(j==i){
			s[i][j]=s[i][j-1];
			if(flag) s[i][j]+=1;
		}else{
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
			if(yh[i][j]%k==0) s[i][j]+=1;
		}
	}
	
	return;
}

int main()
{
	ios::sync_with_stdio();
	
	int t,k;
	int maxx=INT_MIN;
	cin>>t>>k;
	
	for(int i=1;i<=t;i++)
	{
		cin>>question[0][i]>>question[1][i];
		if(question[0][i]>maxx) maxx=question[0][i];
	}
	
	build(maxx,k);
	/*
	for(int i=0;i<=maxx;i++)
	{
		for(int j=0;j<=i;j++) cout<<yh[i][j]<<" ";
		cout<<endl;
	}
	
	for(int i=0;i<=maxx;i++)
	{
		for(int j=0;j<=i;j++) cout<<s[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
	*/
	for(int i=1;i<=t;i++)
	{
		int& n=question[0][i];
		int& m=question[1][i];
		
		cout<<s[n][min(n,m)]<<endl;
	}
	
	return 0;
}