math/factorial.hpp

• View this file on GitHub
• Last update: 2024-02-16 18:48:16+09:00
• Include: #include "math/factorial.hpp"

Depends on

• テンプレート (template/template.hpp)

Required by

• Formal Power Series (Sparse) (fps/fps_sparse.hpp)
• $f(x + c)$ (fps/taylor_shift.hpp)

Verified with

• test/math/Binomial_Coefficient.test.cpp
• test/polynomial/Exp_of_FPS_Sparse.test.cpp
• test/polynomial/Inv_of_FPS_Sparse.test.cpp
• test/polynomial/Log_of_FPS_Sparse.test.cpp
• test/polynomial/Polynomial_Taylor_Shift.test.cpp
• test/polynomial/Pow_of_FPS_Sparse.test.cpp

Code

#pragma once

#include"../template/template.hpp"

namespace lib {

template<typename T>
struct Binom{
    Binom(int lim = 300000){
        if (kaijo.empty()){
            kaijo = {1,1};
            kainv = {1,1};
        }
        extend(lim);
    }
    static T fact(int x) {
        if (x < 0) return T(0);
        return kaijo[x];
    }
    static T ifact(int x){
        if (x < 0) return T(0);
        return kainv[x];
    }
    static T C(int n, int r){
        if (n < 0 || n < r || r < 0) return T(0);
        return kaijo[n] * kainv[r] * kainv[n-r];
    }
    static T P(int n, int r){
        if (n < 0 || n < r || r < 0) return T(0);
        return kaijo[n] * kainv[n-r];
    }
    static T Inv(int n){
        assert(0 < n);
        return ifact(n) * fact(n-1);
    }
    T operator()(int n, int r){ return C(n,r); }
  private:
    static vector<T> kaijo, kainv;
    static void extend(int lim){
        if ((int)kaijo.size() > lim) return ;
        int pre = kaijo.size();
        kaijo.resize(lim+1);
        kainv.resize(lim+1);
        for (int i = pre; i <= lim; i++) kaijo[i] = kaijo[i-1] * T(i);
        kainv[lim] = kaijo[lim].inv();
        for (int i = lim-1; i >= pre; i--) kainv[i] = kainv[i+1] * T(i+1);
    }
};
template<typename T>
vector<T>Binom<T>::kaijo = vector<T>(2,T(1));
template<typename T>
vector<T>Binom<T>::kainv = vector<T>(2,T(1));

} // namespace lib

#line 2 "math/factorial.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "math/factorial.hpp"

namespace lib {

template<typename T>
struct Binom{
    Binom(int lim = 300000){
        if (kaijo.empty()){
            kaijo = {1,1};
            kainv = {1,1};
        }
        extend(lim);
    }
    static T fact(int x) {
        if (x < 0) return T(0);
        return kaijo[x];
    }
    static T ifact(int x){
        if (x < 0) return T(0);
        return kainv[x];
    }
    static T C(int n, int r){
        if (n < 0 || n < r || r < 0) return T(0);
        return kaijo[n] * kainv[r] * kainv[n-r];
    }
    static T P(int n, int r){
        if (n < 0 || n < r || r < 0) return T(0);
        return kaijo[n] * kainv[n-r];
    }
    static T Inv(int n){
        assert(0 < n);
        return ifact(n) * fact(n-1);
    }
    T operator()(int n, int r){ return C(n,r); }
  private:
    static vector<T> kaijo, kainv;
    static void extend(int lim){
        if ((int)kaijo.size() > lim) return ;
        int pre = kaijo.size();
        kaijo.resize(lim+1);
        kainv.resize(lim+1);
        for (int i = pre; i <= lim; i++) kaijo[i] = kaijo[i-1] * T(i);
        kainv[lim] = kaijo[lim].inv();
        for (int i = lim-1; i >= pre; i--) kainv[i] = kainv[i+1] * T(i+1);
    }
};
template<typename T>
vector<T>Binom<T>::kaijo = vector<T>(2,T(1));
template<typename T>
vector<T>Binom<T>::kainv = vector<T>(2,T(1));

} // namespace lib

Back to top page