q-Analogs
(math/q_analogs.hpp)

• View this file on GitHub
• Last update: 2024-01-06 12:43:38+09:00
• Include: #include "math/q_analogs.hpp"

Description

$q$-数, $q$-階乗, $q$-二項係数を計算する．

空間計算量: $O(n)$

Operations

• qAnalogs(mint q, int n)
  • $n$ 以下の非負整数の $q$-数， $q$-階乗及びその逆元を前計算する
  • 時間計算量: $O(n)$
• T number(int n)
  • $[n]_q$ を返す
  • 時間計算量: $O(1)$
• T fact(int n)
  • $[n]_q!$ を返す
  • 時間計算量: $O(1)$
• T fact_inv(int n)
  • $[n]_q!$ の逆元を返す
  • 時間計算量: $O(1)$
• T binom(int n, int k)
  • $\binom{n}{k}_q$ を返す
  • 時間計算量: $O(1)$

Reference

• ABC278 Ex - make 1 解説
• verify: https://atcoder.jp/contests/abc278/submissions/49047601

Code

#pragma once
#include <cassert>
#include <vector>

template <typename mint>
class qAnalogs {
   public:
    qAnalogs() = default;
    explicit qAnalogs(mint q, int n)
        : q(q), num(n + 1), fact_(n + 1), fact_inv_(n + 1) {
        for (int k = 1; k <= n; ++k) {
            num[k] = num[k - 1] * q + 1;
        }
        fact_[0] = 1;
        for (int k = 1; k <= n; ++k) {
            fact_[k] = fact_[k - 1] * num[k];
        }
        fact_inv_[n] = mint(1) / fact_[n];
        for (int k = n; k > 0; --k) {
            fact_inv_[k - 1] = fact_inv_[k] * num[k];
        }
    }

    mint number(int n) {
        assert(0 <= n && n < (int)num.size());
        return num[n];
    }

    mint fact(int n) {
        assert(0 <= n && n < (int)fact_.size());
        return fact_[n];
    }

    mint fact_inv(int n) {
        assert(0 <= n && n < (int)fact_inv_.size());
        return fact_inv_[n];
    }

    mint binom(int n, int k) {
        assert(0 <= n && n < (int)fact_.size());
        if (k < 0 || n < k) return 0;
        return fact_[n] * fact_inv_[k] * fact_inv_[n - k];
    }

   private:
    const mint q;
    std::vector<mint> num, fact_, fact_inv_;
};

#line 2 "math/q_analogs.hpp"
#include <cassert>
#include <vector>

template <typename mint>
class qAnalogs {
   public:
    qAnalogs() = default;
    explicit qAnalogs(mint q, int n)
        : q(q), num(n + 1), fact_(n + 1), fact_inv_(n + 1) {
        for (int k = 1; k <= n; ++k) {
            num[k] = num[k - 1] * q + 1;
        }
        fact_[0] = 1;
        for (int k = 1; k <= n; ++k) {
            fact_[k] = fact_[k - 1] * num[k];
        }
        fact_inv_[n] = mint(1) / fact_[n];
        for (int k = n; k > 0; --k) {
            fact_inv_[k - 1] = fact_inv_[k] * num[k];
        }
    }

    mint number(int n) {
        assert(0 <= n && n < (int)num.size());
        return num[n];
    }

    mint fact(int n) {
        assert(0 <= n && n < (int)fact_.size());
        return fact_[n];
    }

    mint fact_inv(int n) {
        assert(0 <= n && n < (int)fact_inv_.size());
        return fact_inv_[n];
    }

    mint binom(int n, int k) {
        assert(0 <= n && n < (int)fact_.size());
        if (k < 0 || n < k) return 0;
        return fact_[n] * fact_inv_[k] * fact_inv_[n - k];
    }

   private:
    const mint q;
    std::vector<mint> num, fact_, fact_inv_;
};

Back to top page