Jennie

k是给定的

把m和n扔到一个坐标系里

成了二维的了，我们又都知道$C^mn=c{n-1}^{m-1}+c_{n-1}^m$

然后求和那个奇特的范围

这就是个二维的前缀和啊

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#define lll long longa
using namespace std;
int c[3000][3000];
int sum[3000][3000];
int t,k;
int n,m;
void ini(){
    c[1][1]=1;
    for(int i=0;i<=2000;++i){
        c[i][0]=1;
    }
    for(int i=2;i<=2000;++i){
        for(int j=1;j<=i;++j){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(c[i][j]==0);
        }
        sum[i][i+1]=sum[i][i];
    }
}
int main(){
    scanf("%d%d",&t,&k);
    ini();
    while(t--){
        scanf("%d%d",&n,&m);
        if(m>n) m=n;
        cout<<sum[n][m]<<endl;
    }
    return 0;
}