lp2822 NOIP2016 组合数问题

基础数论题。
首先我们知道，任何数的逆元模k，都不可能等于零。
故而我们不必考虑k是否是质数。
然后我们考虑先预处理出哪些\(n,m\)满足\(C_{n}^{m}≡0(mod\ k)\)
接着前缀和即可。
由于\(n,m\)较小，可以考虑用递推。

#include<iostream>
#include<cstdio> 
#include<cstring>
using namespace std;
int sm[2005][2005],C[2005][2005];
int n,m,k;
void prpr(){
    memset(sm,0,sizeof(sm));
    C[0][0]=C[1][1]=1;
    for(int i=1;i<=2000;++i){
        C[i][0]=1,C[i][i]=1;
    }
    for(int i=2;i<=2000;++i){
        for(int j=1;j<=i;++j){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;
        }
    }
    for(int i=2;i<=2000;++i){
        for(int j=1;j<=i;++j){
            sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1];
            if(C[i][j]==0){
                ++sm[i][j];
            }
        }
        sm[i][i+1]=sm[i][i];
    }
}
void init(){
    scanf("%d%d",&n,&m);
    printf("%d\n",(m>n)?(sm[n][n]):(sm[n][m]));
}
int main(){
    int T;
    scanf("%d%d",&T,&k);
    prpr();
    while(T--){
        init();
    }
    return 0;
}