パスカルの三角形 (Pascal's triangle)
(include/emthrm/math/twelvefold_way/pascal.hpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/math/twelvefold_way/pascal.hpp"

二項係数 (binomial coefficients)

\[\binom{n}{k} = \binom{n - 1}{r - 1} + \binom{n - 1}{r} = \frac{n!}{k!\,(n - k)!}\]

時間計算量

	時間計算量
パスカルの三角形	$O(N^2)$
二項係数	$\langle O(N + \log{M}), O(1) \rangle$
二項係数 巨大な $n$ 版	$O(K + \log{M})$
二項係数の数表 巨大な $n$ 版	$O(K)$

仕様

パスカルの三角形

名前	戻り値
template <typename T> std::vector<std::vector<T>> pascal(const int n);	$n$ 段のパスカルの三角形

二項係数

二項係数 巨大な $n$ 版

二項係数の数表 巨大な $n$ 版

名前	戻り値
template <unsigned int T> std::vector<MInt<T>> large_nCk_init(long long n, const int k);	$\binom{n}{r}$ ($0 \leq r \leq k$) の数表

参考文献

http://drken1215.hatenablog.com/entry/2018/06/08/210000

パスカルの三角形

• Blaise Pascal: Traité du triangle arithmétique , avec quelques autres petits traitez sur la mesme matière (1665).

TODO

• https://w.atwiki.jp/uwicoder/pages/2118.html
• https://ferin-tech.hatenablog.com/entry/2018/01/17/010829
• https://qiita.com/Kiri8128/items/dfdadf85ba2ea14026b6
• https://judge.yosupo.jp/problem/binomial_coefficient
• $\sum_{i = 0}^M \binom{N}{i}$
  • https://nyaannyaan.github.io/library/modulo/multipoint-binomial-sum.hpp.html
  • https://twitter.com/noshi91/status/1349778791262945280
  • https://atcoder.jp/contests/abc235/tasks/abc235_g
  • https://yukicoder.me/problems/no/2206

Submissons

• パスカルの三角形
• 二項係数
• 二項係数 巨大な $n$ 版
• 二項係数の数表 巨大な $n$ 版

Verified with

• 数学/写像12相/パスカルの三角形 (test/math/twelvefold_way/pascal.test.cpp)

Code

#ifndef EMTHRM_MATH_TWELVEFOLD_WAY_PASCAL_HPP_
#define EMTHRM_MATH_TWELVEFOLD_WAY_PASCAL_HPP_

#include <vector>

namespace emthrm {

template <typename T>
std::vector<std::vector<T>> pascal(const int n) {
  std::vector<std::vector<T>> c(n + 1, std::vector<T>(n + 1, 0));
  for (int i = 0; i <= n; ++i) {
    c[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
  }
  return c;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_TWELVEFOLD_WAY_PASCAL_HPP_

#line 1 "include/emthrm/math/twelvefold_way/pascal.hpp"



#include <vector>

namespace emthrm {

template <typename T>
std::vector<std::vector<T>> pascal(const int n) {
  std::vector<std::vector<T>> c(n + 1, std::vector<T>(n + 1, 0));
  for (int i = 0; i <= n; ++i) {
    c[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
  }
  return c;
}

}  // namespace emthrm

Back to top page