峰狂算法

发表于 更新于 分类于 Waline： 本文字数： 205 阅读时长 ≈ 1 分钟

排列组合

技巧

具体参考链接

模板

如果对\(\left( \begin{array}{c} n\\ m\\ \end{array} \right)\)组合数轮询并不多，按照定义求单个组合数即可

1
2
3
4
5
6
7
8
ll c(int n, int m) {
  ll ans = 1;
  for (int i = n; i > n - m; --i) {
    ans *= i;
    ans /= (n + 1 - i);
  }
  return ans;
}

如果轮询次数过多，还是用杨辉三角打表吧：

1
2
3
4
5
6
for (int i = 0; i <= N; ++i) {
  c[i][0] = c[i][i] = 1;
  for (int j = 1; j < i; ++j) {
    c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
  }
}

练习题

  • P2822 杨辉三角模板题，二维前缀和优化
  • P1246 组合数的精髓：可视作任意顺序
  • P2638 插板法+高精度
  • P2789 分组后使用乘法原理
  • P3913 分组后使用乘法原理
  • P1866 贪心优化运算
  • P2415 组合数的求和

卡特兰数

0%