锐客网

  1. 首页 > it技术 > >

总结|学组合数学心得与题解（一）——组合计数

今天我在某网站上稍微学习了一下组合数学，准确来讲，今天就看了看组合计数。像一些弱智的排列数、组合数大家肯定在小学奥数就已经精通了（只有我这种蒟蒻忘的精光）。当然，博主比较菜，连二项式定理、帕斯卡恒等式都不会，所以今天只能恶补一下啦。
排列数与组合数大家一定都十分的明白了，所以我在这里也不多说了。
然后二项式定理以及帕斯卡恒等式就是俩公式，自己看看就好了。
今天我做了两道题（貌似特别菜，专适我这种蒟蒻）：
1.总结|学组合数学心得与题解（一）——组合计数
文章图片

解析：这道题看起来十分菜，直接用二项式定理就好了，把px和qy看成一个整体就好。但是写组合数的函数时千万不要直接搞或者用递归，不然。。。就会像我一样超时n次，最好直接用帕斯卡恒等式递推预处理出每组组合数的值（不要忘了边加边取模哦）
代码：

#include using namespace std; typedef long long LL; typedef double DB; const int MOD = 1e4 + 7; int Max(int a, int b){return a > b ? a : b; } int Min(int a, int b){return a < b ? a : b; }int C(int n, int r){ //cout< n / 2 + 1) r = n - r; ans = ((C(n - 1, r - 1) % MOD) + C(n - 1, r)) % MOD; return ans; } }int qpow(int l, int r){ int res = 1; while(r){ if(r & 1) res = res * l % MOD; l = l * l % MOD; r >>= 1; } return res; }int C1(int m, int k){ int count = 0; for(int i = m; i >= k; i --){ if (k > 1) C1(i - 1, k - 1); else count ++; } return count; }inline int read(){ int r = 0, z = 1; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-') z = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){r = r * 10 + ch - '0'; ch = getchar(); } return r * z; } void fre(){ freopen(".in", "r", stdin); freopen(".out", "w", stdout); } void init(){ int p = read(), q = read(), k = read(), a = read(), b = read(); int ans = ((C1(k, b) * qpow(p, a)) % MOD * qpow(q, b)) % MOD; int ans1 = qpow(p, a) * qpow(q, b); cout

2.
总结|学组合数学心得与题解（一）——组合计数
文章图片

样例输入1：
5 2 1 2 3 4 5

样例输出1：
40

【总结|学组合数学心得与题解（一）——组合计数】解析：这道题其实也是很简单的，只要仔细一想，就能知道正解。
我们首先先把这一列数从大到小排序，然后和最大的数在一组的k个数，其辣度值就是其本身，如果这k个数中定了这个最大的数，可以在n-1个数中调出k-1个数与这个最大的数组成一组，这样的方案数是C(n?1,k?1)，总辣度值就是C(n?1,k?1)×最大的数a[1]。
我们再找到次大的数。这是我们排除最大的数，从剩下的n-2个数中调出k-1个数与这个次大的数组成一组，这时所组成的组的辣度值都是这个次大的数这样的总方案数是C(n?2,k?1)，总辣度值是C(n?2,k?1)×次大的数a[2]。
以此类推，建议中间值开个long long，要不然有可能WA掉。
代码：
#include using namespace std; typedef long long LL; typedef double DB; const int MAXN = 1e5 + 30; const int MOD = 1e9 + 7; int c[MAXN][61], a[MAXN]; int Max(int a, int b){return a > b ? a : b; } int Min(int a, int b){return a < b ? a : b; }void C(int n, int k){ c[0][0] = 1; for(int i = 1; i <= n; i ++){ c[i][0] = 1; for(int j = 1; j <= Min(k, i); j ++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD; } }int cmp(int x, int y){return x > y; }inline int read(){ int r = 0, z = 1; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-') z = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){r = r * 10 + ch - '0'; ch = getchar(); } return r * z; }void fre(){ freopen(".in", "r", stdin); freopen(".out", "w", stdout); } void init(){ int n = read(), k = read(); LL ans = 0; C(n, k); //out<

    推荐阅读


    上一篇：Apache Flink 入门 (第三篇)(在YARN上运行Flink任务)

    下一篇：spark-streaming 编程(五)updateStateByKey