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

Trick

$$S$$是可以递推的

• $$S(n, m + 1) = S(n, m) + C_{n}^{m + 1}$$

• $$S(n + 1, m) = 2S(n, m) - C_n^m$$

$$S(n, m)$$可以看做是杨辉三角上的一行，而$$S(n+1, m)$$是他的下一行

#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);

}

0 条评论

相关文章

1432

2926

神、上帝以及老天爷（递推） - HDU 248

HDU 2006'10 ACM contest的颁奖晚会隆重开始了！为了活跃气氛，组织者举行了一个别开生面、奖品丰厚的抽奖活动，这个活动的具体要求是这样的： ...

1652

21310

1270

Leetcode 123 Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock o...

7616

1272