一种递推组合数前缀和的Trick

#include<bits/stdc++.h>
using namespace std;
int N, M, Lim, C[1001][1001], S[1001][1001];
int Make1() {
    for(int i = 0; i <= Lim; i++) {
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];        
    }
    return C[N][M];
}
void Make2() {
    /*for(int i = 0; i <= Lim; i++) {
        S[i][0] = 1;
        for(int j = 1; j <= i; j++)
            S[i][j] = S[i][j - 1] + C[i][j];        
    }*/
    for(int i = 0, base = 1; i <= Lim; i++, base <<= 1) {
        S[i][i] = base;
        for(int j = i + 1; j <= Lim; j++)
            S[j][i] = 2 * S[j - 1][i] - C[j - 1][i];        
    }
}
void print(int (*a)[1001]) {
    for(int i = 0; i <= Lim; i++, puts("")) {
        for(int j = 0; j <= i; j++)
            printf("%d ", S[i][j]);     
    }
}
main() {
    Lim = 10;
    //cin >> N >> M;
    Make1();
    Make2();
    print(S);
    
}