组合数问题

排列组合
组合公式

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int a[N][N],b[N][N];//a储存模k的余数，b储存是否为k的倍数
int main(){
    int t,k;
    scanf("%d%d",&t,&k);
    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            if(!j) a[i][j]=1;//当j为0时模为1
            else a[i][j]=(a[i-1][j-1]+a[i-1][j])%k;//排列组合公式C(m,n)=C(m-1,n-1)+C(m-1,n)
            if(!a[i][j]) b[i][j]=1;//为k的倍数时储存1
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(i) b[i][j]+=b[i-1][j];//行累加
            if(j) b[i][j]+=b[i][j-1];//列累加
            if(i&&j) b[i][j]-=b[i-1][j-1];//此时重复了b[i-1][j-1];
        }
    }
    int n,m;
    while(t--){
        scanf("%d%d",&n,&m);
        printf("%d\n",b[n][m]);
    }
    return 0;
}