记录编号	544880	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]组合数问题	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	1.429 s
提交时间	2019-10-23 19:40:25	内存使用	75.31 MiB

#include<bits/stdc++.h>
using namespace std;
long long t,n,m,k,f[2000+10][2000+10],s[2000+10][2000+10];
int main()
{
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
	scanf("%lld%lld",&t,&k);
    for(int i=0;i<=2000;i++)
        {
            f[i][i]=1;
            f[i][0]=1;
        }
    for(int i=1;i<=2000;i++)
        for(int j=1;j<i;j++)
        {
            f[i][j]=(f[i-1][j-1]+f[i-1][j])%k;
        }
    for(int i=1;i<=2000;i++)
        for(int j=1;j<=2000;j++)
        {
             s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1];
                if(f[i][j]==0&&j<=i)
                    s[i][j]++;
        }
    for(int i=1;i<=t;i++)
    {
        long long ans=0;
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",s[n][m]);
    }
}