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

记录一下一种推组合数前缀和的方法

Trick

设\(\sum_{i = 0}^m C_n^i = S(n, m)\)

\(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)\)是他的下一行

考虑组合数的递推公式,除了\(C[n][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 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

水果Fruit(母函数) - HDU 2152

转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

1432
来自专栏数说工作室

循环、分支...都可以在Python中用函数实现! | 函数式编程,打开另一个世界的大门

编程界有一位传奇人物——王垠,介绍一下他的退学经历,对,你没听错,退!学!经!历!: 2006年,从清华大学计算机系退学,在水木社区BLOG上发表了《清华梦的...

2926
来自专栏ACM算法日常

神、上帝以及老天爷(递推) - HDU 248

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

1652
来自专栏企鹅号快讯

C+虚函数实现多态性的思考

相信这篇文字已经被这个晦涩的标题直接给PASS了,但笔者想把这些晦涩的概念说的生动些,C++和Python在编程思想上有很多是一致的,比如面向对象的思想,面向对...

21310
来自专栏算法channel

除自身累乘算法题,又有创意解法了

一个数组,求除了某元素自身位置之外的其他元素累积相乘,返回一个同长度的数组。有两个要求比较苛刻: 1) 不能用除法 2) 时间复杂度O(n),空间复杂度O(1)...

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
来自专栏aCloudDeveloper

算法导论第二章小试牛刀

Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于...

28210
来自专栏Code_iOS

数据结构?

数据结构可以实现一种或多种抽象数据类型,而抽象数据类型(Abstract Data Type [ADT])就是一种数学的抽象,一些操作的集合【插入、删除等操作】...

1332
来自专栏我杨某人的青春满是悔恨

函数式思维

自从大四看了三章《SICP》之后我就自诩为一个函数式编程爱好者,之前也在公司分享过一个 Haskell 的 Topic,效果非常糟糕,讲到后来已经没剩几个人了,...

1001
来自专栏云时之间

算法导论系列:分治算法

说起分治法,大家一定也都听过秦始皇采用郡县制将国家分为三十六郡的故事,我们常说”山高皇帝远”,意思就是山高路远,皇帝都管不了,实际上无论皇帝多远,山有多高,整个...

1272

扫码关注云+社区

领取腾讯云代金券