math/stirling2.hpp

View this file on GitHub
Last update: 2021-09-12 23:20:08-04:00
Include: #include "math/stirling2.hpp"

Depends on

Verified with

tests/math/stirling2.test.cpp

Code

#include "../template.hpp"
#include "choose.hpp"
#pragma once

// Stirling Numbers (2nd kind)
// Depends on mod and nchooser templates (and calling init_nchooser to init factorial table)
// Number of ways to partition N labelled objects into K (NONEMPTY) unlabelled subsets (order of subsets does not matter)
// If you want to do it with labelled subsets, just remove the division at the end or multiply by fact[K]
// If empty subsets were allowed, the answer would just be K^N
template <typename T> T stir2(int N, int K, Choose<T> &c) {
    T res = 0, coeff = 1;
    for (int i = 0; i <= K; i++) {
        res += coeff * c.choose(K, i) * T::pow(K - i, N);
        coeff *= -1;
    }
    return res / c.fact[K];
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.6/x64/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/Python/3.10.6/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.10.6/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.10.6/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: math/choose.hpp: line 2: #pragma once found in a non-first line