library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Prefix Sum of Binomial Coefficient
(Math/prefixbinom.hpp)

• View this file on GitHub
• Last update: 2026-10-28 08:02:01+09:00
• Include: #include "Math/prefixbinom.hpp"

Depends on

• Mo's Algorithm (Algorithm/mo.hpp)

Code

#pragma once
#include "Algorithm/mo.hpp"

template <typename T>
vector<T> PrefixSumOfBinomial(const vector<pair<int, int>> &qs) {
    int N = 2;
    for (auto &p : qs)
        N = max(N, p.first);
    int Q = qs.size();
    Mo mo(N);
    for (auto &p : qs) {
        mo.add(p.second, p.first);
    }
    vector<T> ans(Q);
    T cur = 1;
    int n = 0, m = 0;
    auto al = [&](int) { cur -= nCr<T>(n, m--); };
    auto ar = [&](int) { cur += cur - nCr<T>(n++, m); };
    auto el = [&](int) { cur += nCr<T>(n, ++m); };
    auto er = [&](int) { cur = (cur + nCr<T>(--n, m)) * Inv<T>(2); };
    auto q = [&](int i) { ans[i] = cur; };
    mo.run(al, ar, el, er, q);
    return ans;
}

/**
 * @brief Prefix Sum of Binomial Coefficient
 */

#line 2 "Algorithm/mo.hpp"

struct Mo{
    const int n;
    vector<int> L,R;
    Mo(int _n):n(_n){}
    void add(int lb,int rb){
        L.push_back(lb);
        R.push_back(rb);
    }
    template <typename AL, typename AR, typename DL, typename DR, typename OUT>
    void run(const AL& addl,const AR& addr,const DL& dell,const DR& delr,const OUT& out){
        const int q=L.size();
        const int w=max<int>(1,1.0*n/max<double>(1.0,sqrt(q*2.0/3.0)));
        vector<int> ord(q);
        iota(ALL(ord),0);
        sort(ALL(ord),[&](int i,int j){
            int a=L[i]/w,b=L[j]/w;
            if(a!=b)return a<b;
            if(a&1)return R[i]<R[j];
            else return R[i]>R[j];
        });
        int lb=0,rb=0;
        for(auto& i:ord){
            while(lb>L[i])addl(--lb);
            while(rb<R[i])addr(rb++);
            while(lb<L[i])dell(lb++);
            while(rb>R[i])delr(--rb);
            out(i);
        }
    }
};

/**
 * @brief Mo's Algorithm
 * @docs docs/mo.md
 */
#line 3 "Math/prefixbinom.hpp"

template <typename T>
vector<T> PrefixSumOfBinomial(const vector<pair<int, int>> &qs) {
    int N = 2;
    for (auto &p : qs)
        N = max(N, p.first);
    int Q = qs.size();
    Mo mo(N);
    for (auto &p : qs) {
        mo.add(p.second, p.first);
    }
    vector<T> ans(Q);
    T cur = 1;
    int n = 0, m = 0;
    auto al = [&](int) { cur -= nCr<T>(n, m--); };
    auto ar = [&](int) { cur += cur - nCr<T>(n++, m); };
    auto el = [&](int) { cur += nCr<T>(n, ++m); };
    auto er = [&](int) { cur = (cur + nCr<T>(--n, m)) * Inv<T>(2); };
    auto q = [&](int i) { ans[i] = cur; };
    mo.run(al, ar, el, er, q);
    return ans;
}

/**
 * @brief Prefix Sum of Binomial Coefficient
 */

Back to top page