Pascal's Triangle (ナイーブな二項係数テーブル)
(src/math/Pascal-Triangle.hpp)

• View this file on GitHub
• Last update: 2022-10-21 17:48:21+09:00
• Include: #include "src/math/Pascal-Triangle.hpp"

概要

Pascal_Triangle<T>(int max_n, int max_r)

愚直に二項係数テーブルを構築する

機能

• コンストラクタ: $\dbinom{n}{r}$ について、使いたい最大の $n$ と $r$ を引数にとる
• ncr(int n, int r): $\dbinom{n}{r}$ を返す

計算量

• テーブル構築 $O(NR)$
• 取得 $O(1)$

Verified with

• test/Pascal-Triangle.test.cpp

Code

#pragma once

#include <vector>

namespace zawa {

template <class T>
class Pascal_Triangle {
private:
    std::vector<std::vector<T>> table;
public:
    Pascal_Triangle(int max_n, int max_r)
        : table(max_n + 1, std::vector<T>(max_r + 1)) {
        table[0][0] = 1;
        for (int i = 1 ; i <= max_n ; i++) {
            for (int j = 1 ; j <= max_r ; j++) {
                table[i][j] = table[i - 1][j - 1] + table[i - 1][j];
            }
        }
    }

    T ncr(int n, int r) {
        return table.at(n).at(r);
    }
};

} // namespace zawa

#line 2 "src/math/Pascal-Triangle.hpp"

#include <vector>

namespace zawa {

template <class T>
class Pascal_Triangle {
private:
    std::vector<std::vector<T>> table;
public:
    Pascal_Triangle(int max_n, int max_r)
        : table(max_n + 1, std::vector<T>(max_r + 1)) {
        table[0][0] = 1;
        for (int i = 1 ; i <= max_n ; i++) {
            for (int j = 1 ; j <= max_r ; j++) {
                table[i][j] = table[i - 1][j - 1] + table[i - 1][j];
            }
        }
    }

    T ncr(int n, int r) {
        return table.at(n).at(r);
    }
};

} // namespace zawa

Back to top page