math/binomial_prefix_sum.hpp

• View this file on GitHub
• Last update: 2026-06-22 00:51:32+09:00
• Include: #include "math/binomial_prefix_sum.hpp"

Depends on

• math/binomial.hpp
• misc/mo_algorithm.hpp

Code

#pragma once

#include"math/binomial.hpp"
#include"misc/mo_algorithm.hpp"

namespace noya2 {

template<typename mint>
struct binomial_prefix_sum {
    int m;
    std::vector<mint> table;
    binomial<mint> binom;
    binomial_prefix_sum() {}
    binomial_prefix_sum(int nmax){
        m = sqrt(nmax) + 1;
        table.resize(m * m);
        // 0 <= i, j < m
        // table[i * m + j] = sum_{k in [0, j * m + m)} binom{i * m + m}{k}
        for (int i = 0; i < m; i++){
            mint sum = 0;
            int n = i * m + m;
            int j = 0;
            for (int k = 0; k <= n; k++){
                sum += binom(n, k);
                if ((k + 1) % m == 0){
                    assert(k + 1 == j * m + m);
                    table[i * m + j] = sum;
                    j++;
                }
            }
            // for ( ; j < m; j++){
            //     table[i * m + j] = sum;
            // }
        }
    }
    // sum_{i in [0, k)} binom{n}{i}
    mint operator()(int n, int k){
        if (k <= 0){
            return 0;
        }
        if (k >= n+1){
            return mint(2).pow(n);
        }
        if (k < m){
            mint ans = 0;
            for (int i = 0; i < k; i++){
                ans += binom(n, i);
            }
            return ans;
        }
        // n >= k >= m
        int i = (n - m) / m;
        int j = (k - m) / m;
        mint ans = table[i * m + j];
        int nn = i * m + m, kk = j * m + m;
        while (nn < n){
            ans *= 2;
            ans -= binom(nn, kk - 1);
            nn++;
        }
        while (kk < k){
            ans += binom(n, kk);
            kk++;
        }
        return ans;
    }
};

// for nks[i] = {n, k}, ret[i] = \sum_{i in [0, k)} binom{n}{i}
template<typename mint>
std::vector<mint> multipoint_binomial_prefix_sum(std::vector<std::pair<int, int>> nks){
    int q = nks.size();
    int mx = 0;
    for (auto [n, k] : nks){
        if (mx < n) mx = n;
    }
    mo_algorithm mo(mx + 1, q);
    binomial<mint> binom;
    for (auto [n, k] : nks){
        mo.insert(std::clamp(k, 0, n + 1), n);
    }
    int n = 0, k = 0;
    mint cur = 0;
    auto addl = [&](int kk){
        cur -= binom(n, --k);
    };
    auto dell = [&](int kk){
        cur += binom(n, k++);
    };
    const mint i2 = mint(2).inv();
    auto delr = [&](int){
        cur += binom(n - 1, k - 1);
        cur *= i2;
        n--;
    };
    auto addr = [&](int){
        cur *= 2;
        cur -= binom(n, k - 1);
        n++;
    };
    vector<mint> ans(q);
    auto rem = [&](int i){
        ans[i] = cur;
    };
    mo.run(addl, addr, dell, delr, rem);
    return ans;
}

} // namespace noya2

#line 2 "math/binomial_prefix_sum.hpp"

#line 2 "math/binomial.hpp"

#include<vector>
namespace noya2 {

template<typename mint>
struct binomial {
    binomial(int len = 300000){ extend(len); }
    static mint fact(int n){
        if (n < 0) return 0;
        while (n >= (int)_fact.size()) extend();
        return _fact[n];
    }
    static mint ifact(int n){
        if (n < 0) return 0;
        while (n >= (int)_fact.size()) extend();
        return _ifact[n];
    }
    static mint inv(int n){
        return ifact(n) * fact(n-1);
    }
    static mint C(int n, int r){
        if (!(0 <= r && r <= n)) return 0;
        return fact(n) * ifact(r) * ifact(n-r);
    }
    static mint P(int n, int r){
        if (!(0 <= r && r <= n)) return 0;
        return fact(n) * ifact(n-r);
    }
    static mint catalan(int n){
        return C(n * 2, n) * inv(n + 1);
    }
    inline mint operator()(int n, int r) { return C(n, r); }
    template<class... Cnts>
    static mint M(const Cnts&... cnts){
        return multinomial(0,1,cnts...);
    }
    static void initialize(int len = 2){
        _fact.clear();
        _ifact.clear();
        _fact = {1,1};
        _ifact = {1,1};
        extend(len);
    }
  private:
    static mint multinomial(const int& sum, const mint& div_prod){
        if (sum < 0) return 0;
        return fact(sum) * div_prod;
    }
    template<class... Tail>
    static mint multinomial(const int& sum, const mint& div_prod, const int& n1, const Tail&... tail){
        if (n1 < 0) return 0;
        return multinomial(sum+n1,div_prod*ifact(n1),tail...);
    }
    static std::vector<mint> _fact, _ifact;
    static void extend(int len = -1){
        int siz = _fact.size();
        if (siz == 0){
            _fact = {1,1};
            _ifact = {1,1};
            siz = _fact.size();
        }
        if (len == -1) len = siz * 2;
        len = (int)min<long long>(len, mint::mod() - 1);
        if (len < siz) return ;
        _fact.resize(len+1), _ifact.resize(len+1);
        for (int i = siz; i <= len; i++) _fact[i] = _fact[i-1] * i;
        assert(_fact[len].val() != 0);
        _ifact[len] = _fact[len].inv();
        for (int i = len; i > siz; i--) _ifact[i-1] = _ifact[i] * i;
    }
};
template<typename mint> std::vector<mint> noya2::binomial<mint>::_fact = {1,1};
template<typename mint> std::vector<mint> noya2::binomial<mint>::_ifact = {1,1};

} // namespace noya2
#line 2 "misc/mo_algorithm.hpp"

#line 4 "misc/mo_algorithm.hpp"
#include <algorithm>
#include <functional>
#include <cmath>
#include <numeric>

/*

usage : https://nyaannyaan.github.io/library/modulo/multipoint-binomial-sum.hpp

*/

namespace noya2{

struct mo_algorithm {
    int width;
    std::vector<int> left, right, order;

    mo_algorithm (int n = 1, int q = 1): order(q) {
        width = std::max<int>(1, 1.0 * n / std::max<double>(1.0, std::sqrt(q * 2.0 / 3.0)));
        std::iota(begin(order), end(order), 0);
        left.reserve(q);
        right.reserve(q);
    }

    void insert(int l, int r) { /* [l, r) */
        left.emplace_back(l);
        right.emplace_back(r);
    }

    void run(auto add_left, auto add_right, auto delete_left, auto delete_right, auto rem){
        assert(left.size() == order.size());
        std::sort(begin(order), end(order), [&](int a, int b) {
            int ablock = left[a] / width, bblock = left[b] / width;
            if (ablock != bblock) return ablock < bblock;
            if (ablock & 1) return right[a] < right[b];
            return right[a] > right[b];
            });
        int nl = 0, nr = 0;
        for (auto idx : order) {
            while (nl > left[idx]) add_left(--nl);
            while (nr < right[idx]) add_right(nr++);
            while (nl < left[idx]) delete_left(nl++);
            while (nr > right[idx]) delete_right(--nr);
            rem(idx);
        }
    }
};

} // namespace noya2
#line 5 "math/binomial_prefix_sum.hpp"

namespace noya2 {

template<typename mint>
struct binomial_prefix_sum {
    int m;
    std::vector<mint> table;
    binomial<mint> binom;
    binomial_prefix_sum() {}
    binomial_prefix_sum(int nmax){
        m = sqrt(nmax) + 1;
        table.resize(m * m);
        // 0 <= i, j < m
        // table[i * m + j] = sum_{k in [0, j * m + m)} binom{i * m + m}{k}
        for (int i = 0; i < m; i++){
            mint sum = 0;
            int n = i * m + m;
            int j = 0;
            for (int k = 0; k <= n; k++){
                sum += binom(n, k);
                if ((k + 1) % m == 0){
                    assert(k + 1 == j * m + m);
                    table[i * m + j] = sum;
                    j++;
                }
            }
            // for ( ; j < m; j++){
            //     table[i * m + j] = sum;
            // }
        }
    }
    // sum_{i in [0, k)} binom{n}{i}
    mint operator()(int n, int k){
        if (k <= 0){
            return 0;
        }
        if (k >= n+1){
            return mint(2).pow(n);
        }
        if (k < m){
            mint ans = 0;
            for (int i = 0; i < k; i++){
                ans += binom(n, i);
            }
            return ans;
        }
        // n >= k >= m
        int i = (n - m) / m;
        int j = (k - m) / m;
        mint ans = table[i * m + j];
        int nn = i * m + m, kk = j * m + m;
        while (nn < n){
            ans *= 2;
            ans -= binom(nn, kk - 1);
            nn++;
        }
        while (kk < k){
            ans += binom(n, kk);
            kk++;
        }
        return ans;
    }
};

// for nks[i] = {n, k}, ret[i] = \sum_{i in [0, k)} binom{n}{i}
template<typename mint>
std::vector<mint> multipoint_binomial_prefix_sum(std::vector<std::pair<int, int>> nks){
    int q = nks.size();
    int mx = 0;
    for (auto [n, k] : nks){
        if (mx < n) mx = n;
    }
    mo_algorithm mo(mx + 1, q);
    binomial<mint> binom;
    for (auto [n, k] : nks){
        mo.insert(std::clamp(k, 0, n + 1), n);
    }
    int n = 0, k = 0;
    mint cur = 0;
    auto addl = [&](int kk){
        cur -= binom(n, --k);
    };
    auto dell = [&](int kk){
        cur += binom(n, k++);
    };
    const mint i2 = mint(2).inv();
    auto delr = [&](int){
        cur += binom(n - 1, k - 1);
        cur *= i2;
        n--;
    };
    auto addr = [&](int){
        cur *= 2;
        cur -= binom(n, k - 1);
        n++;
    };
    vector<mint> ans(q);
    auto rem = [&](int i){
        ans[i] = cur;
    };
    mo.run(addl, addr, dell, delr, rem);
    return ans;
}

} // namespace noya2

Back to top page