icpc/binomal.hpp

• View this file on GitHub
• Last update: 2023-05-31 02:53:46+09:00
• Include: #include "icpc/binomal.hpp"
• Link: https://onlinejudge.u-aizu.ac.jp/problems/2751

Depends on

• icpc/template.hpp

Verified with

• verify/aoj_other/aoj_2751.test.cpp

Code

#pragma once

#include "icpc/template.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/2751

template <class T> struct Binomial {
    V<T> f, g;

    Binomial(const int n = 0) {
        f.resize(n);
        g.resize(n);
        f[0] = g[0] = 1;
        for (int i = 1; i < n; i++) f[i] = f[i - 1] * T(i);
        g[n - 1] = T(1) / f[n - 1];
        for (int i = n - 2; i >= 1; i--) g[i] = g[i + 1] * T(i + 1);
    }

    T C(int N, int K) {
        if (N < 0 or K < 0 or N < K) return 0;
        return f[N] * g[N - K] * g[K];
    }

    T P(int N, int K) {
        if (N < 0 or K < 0 or N < K) return 0;
        return f[N] * g[N - K];
    }

    T C_naive(int N, int K) {
        if (N < 0 or K < 0 or N < K) return 0;
        T res(1);
        K = min(K, N - K);
        for (int i = 1; i <= K; i++) {
            res *= N--;
            res /= i;
        }
        return res;
    }
};

#line 2 "icpc/binomal.hpp"

#line 2 "icpc/template.hpp"

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;
template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[ ";
    for (auto& vi : v) os << vi << ", ";
    return os << "]";
}

#ifdef LOCAL
#define show(x) cerr << __LINE__ << " : " << #x << " = " << x << endl;
#else
#define show(x) true
#endif

using uint = unsigned int;
using ull = unsigned long long;

// g++ -g -fsanitize=undefined,address -DLOCAL -std=gnu++17
#line 4 "icpc/binomal.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/2751

template <class T> struct Binomial {
    V<T> f, g;

    Binomial(const int n = 0) {
        f.resize(n);
        g.resize(n);
        f[0] = g[0] = 1;
        for (int i = 1; i < n; i++) f[i] = f[i - 1] * T(i);
        g[n - 1] = T(1) / f[n - 1];
        for (int i = n - 2; i >= 1; i--) g[i] = g[i + 1] * T(i + 1);
    }

    T C(int N, int K) {
        if (N < 0 or K < 0 or N < K) return 0;
        return f[N] * g[N - K] * g[K];
    }

    T P(int N, int K) {
        if (N < 0 or K < 0 or N < K) return 0;
        return f[N] * g[N - K];
    }

    T C_naive(int N, int K) {
        if (N < 0 or K < 0 or N < K) return 0;
        T res(1);
        K = min(K, N - K);
        for (int i = 1; i <= K; i++) {
            res *= N--;
            res /= i;
        }
        return res;
    }
};

Back to top page