offline_binomial_sum

関数 · 複数の二項係数部分和 $\sum_{i=0}^{k}\binom{n}{i}$ をまとめて求める

template <internal::modint mint = modint998>
std::vector<mint> offline_binomial_sum(const std::vector<std::pair<int, int>> &queries);

概要

複数の二項係数部分和 $\sum_{i=0}^{k}\binom{n}{i}$ をまとめて求める

Mo’s algorithmで $(n,k)$ 間を遷移し、各クエリの答えを入力順に返す。

テンプレートパラメータ

パラメータ

戻り値

queriesと同じ長さの列。i番目はi番目のクエリの二項係数部分和

計算量

• クエリ数を $Q$、最大のnを $N$ として $O((N+Q)\sqrt{Q}+Q\log Q)$