acwing523. 组合数问题

题目

题解

c[i][j]=c[i-1][j]+c[i-1][j-1]

#include<iostream>
using namespace std;
const int N=2010;
int T,k;
int c[N][N];
int s[N][N];

int main(){
    cin>>T>>k;
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++){
            if(!j)c[i][j]=1%k;//c[i][0]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
        }
    //二维前缀和
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++){
            if(j<=i&&c[i][j]==0)s[i][j]=1;
            if(i-1>=0)s[i][j]+=s[i-1][j];
            if(j-1>=0)s[i][j]+=s[i][j-1];
            if(i-1>=0&&j-1>=0)s[i][j]-=s[i-1][j-1];
        }
    while(T--){
        int n,m;
        cin>>n>>m;
        cout<<s[n][m]<<endl;
    }
    return 0;
    
}