【NOIP2016】 组合数问题

【题目链接】

          点击打开链接

【算法】

         杨辉三角 + 二维前缀和

         O（1）计算答案

【代码】

         

#include<bits/stdc++.h>
using namespace std;
#define MAXNM 2010

int i,j,n,m,tc,k;
int s[MAXNM+10][MAXNM+10],c[MAXNM+10][MAXNM+10];

int main() {
    
        cin >> tc >> k;
        
        for (i = 0; i <= MAXNM; i++) 
                c[i][0] = c[i][i] = 1;
        for (i = 1; i <= MAXNM; i++) {
                for (j = 1; j < i; j++) {
                        c[i][j] = (c[i-1][j] + c[i-1][j-1]) % k;
                }    
        }
        
        for (i = 1; i <= MAXNM; i++) {
                for (j = 1; j <= MAXNM; j++) {
                        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1];
                        if ((!c[i][j]) && (j <= i)) 
                                s[i][j]++;
                }    
        }
        
        while (tc--) {
                cin >> n >> m;
                cout<< s[n][m] << endl;
        }
        
        return 0;
    
}