二項係数の prefix sum の差分更新部品

components/binomial_prefix_incremental_core.hpp · GitHub で見る

共通ページ

二項係数の prefix sum（差分更新） と 軽量版 の共通部品です。通常は公開ライブラリを使います。

binomial_prefix_detail::IncrementalPrefixSum<Mint, Table, FastHalf> は、直前の問い合わせの状態を保持します。Table は階乗・逆階乗・2 の冪と binom・range を提供する前計算型、FastHalf は mint の内部表現による半分の計算を使うかを指定する bool です。

操作	内容・返り値
IncrementalPrefixSum(max_n=0)	int max_n まで前計算し、状態を (0,0) にする
build(max_n)	前計算と状態を作り直す。返り値は void
max_n()	前計算の上限を int で返す
binom(n,k)	二項係数を Mint で返す。n < 0・k < 0・k > n なら 0
query(n,k)	\(\displaystyle \sum_{i=0}^{k-1}\binom ni\) を Mint で返す。n は int、k は std::int64_t

max_n は非負で INT_MAX 未満かつ素数法未満、query の n は前計算の範囲内とします。query の k は [0,n+1] に収めて扱います。コピーは前計算を共有し、問い合わせの状態は独立します。Mint の条件は公開ライブラリと同じです。FastHalf=true は通常版が mint を使う場合に指定し、それ以外では false とします。NTT・FPS には依存しません。

前計算は \(O(N)\) 時間・空間と逆元計算 1 回です。max_n・binom は \(O(1)\)、query は直前の状態との差を \(\Delta n,\Delta k\) として \(O(\lvert\Delta n\rvert+\lvert\Delta k\rvert)\) 時間・\(O(1)\) 追加空間です。

コード

#ifndef BINOMIAL_PREFIX_INCREMENTAL_CORE_HPP
#define BINOMIAL_PREFIX_INCREMENTAL_CORE_HPP

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <memory>

namespace binomial_prefix_detail {
template<class Mint, class Table, bool FastHalf> class IncrementalPrefixSum {
	std::shared_ptr<const Table> table_;
	int n_ = 0, k_ = 0;
	Mint value_ = Mint(0);
	Mint halve(Mint value) const {
		if constexpr (FastHalf) return Mint::word((value.v + (value.v & 1) * Mint::mod()) >> 1);
		else return value * table_->half;
	}

  public:
	explicit IncrementalPrefixSum(int max_n = 0) : table_(std::make_shared<Table>(max_n)) {}
	void build(int max_n) {
		table_ = std::make_shared<Table>(max_n);
		n_ = k_ = 0;
		value_ = Mint(0);
	}
	int max_n() const { return int(table_->factorial.size()) - 1; }
	Mint binom(int n, int k) const {
		if (n < 0 || k < 0 || k > n) return Mint(0);
		assert(n <= max_n());
		return table_->binom(n, k);
	}
	[[gnu::always_inline]] Mint query(int n, std::int64_t k) {
		assert(0 <= n && n <= max_n());
		int m = int(std::clamp(k, std::int64_t(0), std::int64_t(n) + 1));
		if (m <= 1 || m == n + 1) {
			n_ = n, k_ = m;
			return value_ = m == 0 ? Mint(0) : m == 1 ? Mint(1) : table_->power2[n];
		}
		const Table& table = *table_;
		int row = n_, column = k_;
		Mint value = value_;
		if (column == m) {
			while (row < n) value = value + value - table.binom(row++, column - 1);
			while (row > n) value = halve(value + table.binom(--row, column - 1));
		} else {
			if (!column) row = n;
			while (row < n && column < m) value = value + value + table.binom(row++, column++);
			while (row > n && column > m) value = halve(value - table.binom(--row, --column));
			while (row < n) value = value + value - table.binom(row++, column - 1);
			if (column < m) value += column + 1 == m ? table.binom(row, column) : table.range(row, column, m);
			else if (column > m) value -= m + 1 == column ? table.binom(row, m) : table.range(row, m, column);
			while (row > n) value = halve(value + table.binom(--row, m - 1));
		}
		n_ = n, k_ = m;
		return value_ = value;
	}
};

}

#endif

Back to top page