题目地址：https://www.luogu.org/problemnew/show/P2822

解题思路：

组合数可能会很大，所以要对k取模，模为0则是k的倍数，组合数实际上是杨辉三角（c[i][j]=c[i-1][j]+c[i-1][j-1]，两个的计算方法都是这个式子）

数组c[i][j]即C(i,j)，ans[i][j]存答案，先打表

方法1:

ans[i][j]=ans[i-1][j]-ans[i-1][j-1]+ans[i][j-1];
if(!c[i][j]&&j<=i) ans[i][j]++;

注意：这个时候i,j都是从1～maxn遍历的，因为在求ans[i][j]时，上一行对应的ans[i-1][j]不能为0，否则-a[i-1][j-1]就可能是负数，结果错误

方法2:

只需要根据输入的n的最大值打表，不要建maxn*maxn大小的表
if(!c[i][j])
    ans[i][j]=ans[i-1][j]+1;
else ans[i][j]=ans[i-1][j];

对于组合数数组c[][]的存储有两种方法：只是控制输出的条件不太一样。。搞了好久才知道区别在哪。。太弱了

<figcaption> i和j都从1开始存,实际上就是存了个杨辉三角，第一列都是C(i,0) </figcaption>

<figcaption> i和j都从1开始存，不存杨辉三角的第一列,此时的第一列都是C(i,1) </figcaption>

ac代码：

方法1

#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 2005
using namespace std;
int t,k,n,m;//n>=m
long long  c[maxn][maxn]={0},ans[maxn][maxn]={0};//求组合数的数组和答案数组
void pre_solve()
{
    c[0][0]=1;
    for(int i=1;i<=maxn;i++)
        c[i][i]=c[i][0]=1;
    for(int i=1;i<maxn;i++)
    {
        for(int j=1;j<=i/2;j++)
        {
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
            c[i][i-j]=c[i][j];
        }
    }
    for(int i=1;i<maxn;i++)
    {
        for(int j=1;j<maxn;j++)
        {
            ans[i][j]=ans[i-1][j]-ans[i-1][j-1]+ans[i][j-1];
            if(!c[i][j]&&j<=i) ans[i][j]++;
            //cout<<i<<" "<<j<<" "<<ans[i][j]<<endl;
        }
    }

}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d %d",&t,&k);
    pre_solve();
    while(t--)
    {
        scanf("%d %d",&n,&m);
        printf("%lld\n",ans[n][m]);
    }
    return 0;
}

方法2:

i和j从1开始存，实际上存了个杨辉三角

#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 2005
using namespace std;
int t,k,n,m;//n>=m
long long  c[maxn][maxn]={0},ans[maxn][maxn]={0};//求组合数的数组和答案数组
int maxnn=0,maxm=0;
struct node{
    int n,m;
}a[10001];
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d %d",&t,&k);
    for(int i=0;i<t;i++)
    {
        scanf("%d %d",&a[i].n,&a[i].m);
        maxnn=max(maxnn,a[i].n);
        maxm=max(maxm,a[i].m);
    }
    maxnn++;//！！
    for(int i=1;i<=maxnn;i++)
    {
        c[i][i]=c[i][1]=1;
    }
    for(int i=2;i<=maxnn;i++)
        for(int j=2;j<=i;j++)
         c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
    /*for(int i=1;i<=maxnn;i++) {
        for (int j = 1; j <= maxnn; j++) {
            cout << c[i][j] << " ";
        }
        cout << endl;
    }//输出杨辉三角*/
    for(int i=1;i<=maxnn;i++)
        for(int j=1;j<=i;j++)
        {
            if(!c[i][j])
                ans[i][j]=ans[i-1][j]+1;
            else ans[i][j]=ans[i-1][j];
            //cout<<i<<" "<<j<<" "<<ans[i][j]<<endl;
        }
    for(int i=0;i<t;i++)
    {
        long long res=0;
        for(int j=0;j<=a[i].m+1;j++)//a[i].m+1
        {
            res+=ans[a[i].n+1][j];//a[i].n+1
        }
        printf("%lld\n",res);
    }
    return 0;
}

i和j从1开始存，不存杨辉三角的第一列

#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 2005
using namespace std;
int t,k,n,m;//n>=m
long long  c[maxn][maxn]={0},ans[maxn][maxn]={0};//求组合数的数组和答案数组
int maxnn=0,maxm=0;
struct node{
    int n,m;
}a[10001];
int main()
{
    freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d %d",&t,&k);
    for(int i=0;i<t;i++)
    {
        scanf("%d %d",&a[i].n,&a[i].m);
        maxnn=max(maxnn,a[i].n);
        maxm=max(maxm,a[i].m);
    }
    for(int i=1;i<=maxnn;i++)
    {
        c[i][1]=i%k;//注意这句！
        c[i][i]=1;
    }
    for(int i=2;i<=maxnn;i++)
        for(int j=2;j<i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
    for(int i=1;i<=maxnn;i++)
        for(int j=1;j<=i;j++)
        {
            if(!c[i][j])
                ans[i][j]=ans[i-1][j]+1;
            else ans[i][j]=ans[i-1][j];
        }
    for(int i=0;i<t;i++)
    {
        long long res=0;
        for(int j=0;j<=a[i].m;j++)//a[i].m
        {
            res+=ans[a[i].n][j];//a[i].n
        }
        printf("%lld\n",res);
    }
    return 0;
}