lib/math/enumeration.hpp

• View this file on GitHub
• Last update: 2025-05-22 02:52:27+09:00
• Include: #include "lib/math/enumeration.hpp"

Depends on

• Montgomery modular multiplication (lib/internal/internal_math.hpp)
• 二項係数 (lib/math/combination.hpp)
• lib/math/modint.hpp

Verified with

• test/aoj/dpl/bell.test.cpp
• test/aoj/dpl/stirling.test.cpp

Code

#pragma once
#include <concepts>
#include <vector>
#include "math/combination.hpp"
#include "math/modint.hpp"

template <class mint = modint998>
requires(std::derived_from<mint, internal::modint_base>)
struct Enumeration {
    Enumeration() : _binom(), _data() {}

    mint stirling(int n, int k) {
        mint res = 0;
        for (int i = 0; i < k; ++i) {
            if (i & 1) res -= _binom(k, k - i) * mint(k - i).pow(n);
            else res += _binom(k, k - i) * mint(k - i).pow(n);
        }
        res *= _binom.finv(k);
        return res;
    }

    mint bell(int n, int k) {
        _init(k);
        mint res = 0;
        for (int i = 0; i <= k; ++i) res += mint(i).pow(n) * _binom.finv(i) * _data[k - i];
        return res;
    }

  private:
    Combination<mint> _binom;
    std::vector<mint> _data;

    void _init(int n) {
        if ((int)_data.size() > n) return;
        int m = _data.size();
        _data.resize(n + 1);
        for (int i = m; i <= n; ++i) {
            if (i == 0) _data[i] = 1;
            else if (i & 1) _data[i] = _data[i - 1] - _binom.finv(i);
            else _data[i] = _data[i - 1] + _binom.finv(i);
        }
    }
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: math/combination.hpp: line -1: no such header

Back to top page