軽量な二項係数 prefix sum の内部演算

components/binomial_prefix_core_light.hpp · GitHub で見る

共通ページ · 軽量実装

二項係数の prefix sum の内部演算の高速実装はこちら

軽量な二項係数 prefix sumと差分更新版の共通部品です。通常版 FPS の依存を持たず、light_binomial_prefix_detail::Table<Mint> を使います。

操作・メンバ	内容
Table(n=0) / build(n)	階乗・逆階乗・2 の冪を構築／再構築
binom(n,k)	二項係数。k < 0 または k > n なら 0
center(n)	\(\displaystyle \sum_{i=0}^{\lfloor(n+1)/2\rfloor-1}\binom ni\)
range(n,l,r)	\(\displaystyle \sum_{i=l}^{r-1}\binom ni\)。0 <= l <= r <= n+1 が必要
factorial / inverse_factorial / power2	各前計算の vector<Mint>
half	奇素数法では 2 の逆元

法は素数、構築する上限は非負で INT_MAX 未満かつ法未満にします。各操作の n は構築済みの範囲内で指定します。Mint は公開ライブラリと同じ条件です。

前計算は \(O(n)\) 時間・空間と逆元計算 1 回です。binom・center は \(O(1)\) 時間・追加空間、range は \(O(r-l)\) 時間・\(O(1)\) 追加空間です。

依存ライブラリ

• 32 bit Barrett 演算
• 汎用 modint の階乗・逆階乗生成
• 軽量な階乗・逆階乗テーブル
• modint998244353

検証コード

• test/binomial_prefix_sum_light.test.cpp
• test/binomial_prefix_sum_online_light.test.cpp

コード

#ifndef BINOMIAL_PREFIX_CORE_LIGHT_HPP
#define BINOMIAL_PREFIX_CORE_LIGHT_HPP

#include "factorial_table_light.hpp"
#include <type_traits>

namespace light_binomial_prefix_detail {
template<class Mint> struct Table : light_factorial_detail::Table<Mint> {
	using Base = light_factorial_detail::Table<Mint>;
	using Base::factorial, Base::inverse_factorial;
	std::vector<Mint> power2;
	Mint half;

	explicit Table(int n = 0) : Base(n) {
		assert(std::uint64_t(n) < Mint::mod());
		power2.resize(n + 1);
		power2[0] = Mint(1);
		for (int i = 1; i <= n; ++i) power2[i] = power2[i - 1] + power2[i - 1];
		half = Mint((std::uint64_t(Mint::mod()) + 1) / 2);
	}
	void build(int n) { *this = Table(n); }
	Mint binom(int n, int k) const {
		if (k < 0 || k > n) return Mint(0);
		return factorial[n] * inverse_factorial[k] * inverse_factorial[n - k];
	}
	Mint center(int n) const {
		if (!n) return Mint(0);
		return n & 1 ? power2[n - 1] : (power2[n] - binom(n, n / 2)) * half;
	}
	Mint range(int n, int l, int r) const {
		assert(0 <= l && l <= r && r <= n + 1);
		Mint sum(0);
		for (int i = l; i < r; ++i) sum += inverse_factorial[i] * inverse_factorial[n - i];
		return factorial[n] * sum;
	}
};
}

#endif

Back to top page