library

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

View the Project on GitHub maspypy/library

:heavy_check_mark: mod/prefix_sum_of_binom.hpp

Depends on

Verified with

Code

#include "ds/offline_query/mo.hpp"

template <typename mint>
struct Prefix_Sum_Of_Binom {
  static constexpr u32 mod = mint::get_mod();
  const int MAX_N;
  const int B;
  vc<mint> POW;
  vvc<mint> dat;

  Prefix_Sum_Of_Binom(int MAX_N) : MAX_N(MAX_N), B(sqrt(MAX_N + 1)) {
    assert(MAX_N >= 0);
    int K = ceil(MAX_N, B + B) + 2;
    int p = max(MAX_N, K * B);
    POW.assign(p + 1, mint(1));
    FOR(i, p) POW[i + 1] = POW[i] + POW[i];
    dat.resize(K);
    FOR(k, 0, K) {
      // [0, kB] での closed sum
      vc<mint>& f = dat[k];
      if (MAX_N + 1 - k * B <= 0) continue;
      f.resize(MAX_N + 1 - k * B);
      int m = k * B;
      f[0] = POW[m] * fact<mint>(m);
      FOR(i, MAX_N - m) {
        f[i + 1] = f[i] + f[i] - fact<mint>(i + m) * fact_inv<mint>(i);
      }
    }
  }

  // \sum_{k=0}^{m-1} binom(n,k)
  mint query(int n, int m) {
    assert(0 <= m);
    chmin(m, n + 1);
    if (m == 0) return mint(0);
    if (m + m > n + 1) return POW[n] - query(n, n + 1 - m);
    --m;
    int a = m / B;

    if (m <= a * B + B / 2) {
      u128 t = 0;
      FOR(i, a * B + 1, m + 1) {
        t += u64(fact_inv<mint>(i).val) * (fact_inv<mint>(n - i).val);
      }
      return _get(n, a) + mint::raw(t % mod) * fact<mint>(n);
    } else {
      u128 t = 0;
      FOR(i, m + 1, (a + 1) * B + 1) {
        t += u64(fact_inv<mint>(i).val) * (fact_inv<mint>(n - i).val);
      }
      return _get(n, a + 1) - mint::raw(t % mod) * fact<mint>(n);
    }
    return 0;
  }

 private:
  mint _get(int n, int k) {
    if (n <= k * B) return POW[n];
    return dat[k][n - k * B] * fact_inv<mint>(k * B);
  }
};

template <typename mint>
struct Prefix_Sum_Of_Binom_Offline {
  vc<pair<int, int>> query;

  void add(int n, int m) { query.eb(n, m); }

  vc<mint> calc() {
    int Q = len(query);
    vc<mint> ANS(Q);
    auto I = Mo::get_mo_order(query);
    int n = 0, m = 0;
    mint ans = 0;
    mint inv2 = inv<mint>(2);
    for (auto& i : I) {
      auto [nn, mm] = query[i];
      while (n < nn) {
        ans = ans + ans - C<mint>(n, m - 1);
        n++;
      }
      while (n > nn) {
        ans += C<mint>(n - 1, m - 1);
        ans *= inv2;
        --n;
      }
      while (m < mm) {
        ans += C<mint>(n, m++);
      }
      while (m > mm) {
        ans -= C<mint>(n, --m);
      }
      ANS[i] = ans;
    }
    return ANS;
  }
};
#line 1 "ds/offline_query/mo.hpp"
// Nsqrt(Q)

struct Mo {
  vc<pair<int, int>> LR;
  void add(int L, int R) { LR.emplace_back(L, R); }

  static vc<int> get_mo_order(vc<pair<int, int>> LR) {
    int N = 1;
    for (auto &&[l, r]: LR) chmax(N, l), chmax(N, r);
    int Q = len(LR);
    if (Q == 0) return {};
    int bs = sqrt(3) * N / sqrt(2 * Q);
    chmax(bs, 1);
    vc<int> I(Q);
    iota(all(I), 0);
    sort(all(I), [&](int a, int b) {
      int aa = LR[a].fi / bs, bb = LR[b].fi / bs;
      if (aa != bb) return aa < bb;
      return (aa & 1) ? LR[a].se > LR[b].se : LR[a].se < LR[b].se;
    });

    auto cost = [&](int a, int b) -> int {
      return abs(LR[I[a]].fi - LR[I[b]].fi) + abs(LR[I[a]].se - LR[I[b]].se);
    };

    // ランダムケースで数パーセント

    FOR(k, Q - 5) {
      if (cost(k, k + 2) + cost(k + 1, k + 3)
          < cost(k, k + 1) + cost(k + 2, k + 3)) {
        swap(I[k + 1], I[k + 2]);
      }
      if (cost(k, k + 3) + cost(k + 1, k + 4)
          < cost(k, k + 1) + cost(k + 3, k + 4)) {
        swap(I[k + 1], I[k + 3]);
      }
    }
    return I;
  }

  template <typename F1, typename F2, typename F3, typename F4, typename F5>
  void calc(F1 add_l, F2 add_r, F3 rm_l, F4 rm_r, F5 query) {
    auto I = get_mo_order(LR);
    int l = 0, r = 0;
    for (auto idx: I) {
      while (l > LR[idx].fi) add_l(--l);
      while (r < LR[idx].se) add_r(r++);
      while (l < LR[idx].fi) rm_l(l++);
      while (r > LR[idx].se) rm_r(--r);
      query(idx);
    }
  }
};
#line 2 "mod/prefix_sum_of_binom.hpp"

template <typename mint>
struct Prefix_Sum_Of_Binom {
  static constexpr u32 mod = mint::get_mod();
  const int MAX_N;
  const int B;
  vc<mint> POW;
  vvc<mint> dat;

  Prefix_Sum_Of_Binom(int MAX_N) : MAX_N(MAX_N), B(sqrt(MAX_N + 1)) {
    assert(MAX_N >= 0);
    int K = ceil(MAX_N, B + B) + 2;
    int p = max(MAX_N, K * B);
    POW.assign(p + 1, mint(1));
    FOR(i, p) POW[i + 1] = POW[i] + POW[i];
    dat.resize(K);
    FOR(k, 0, K) {
      // [0, kB] での closed sum
      vc<mint>& f = dat[k];
      if (MAX_N + 1 - k * B <= 0) continue;
      f.resize(MAX_N + 1 - k * B);
      int m = k * B;
      f[0] = POW[m] * fact<mint>(m);
      FOR(i, MAX_N - m) {
        f[i + 1] = f[i] + f[i] - fact<mint>(i + m) * fact_inv<mint>(i);
      }
    }
  }

  // \sum_{k=0}^{m-1} binom(n,k)
  mint query(int n, int m) {
    assert(0 <= m);
    chmin(m, n + 1);
    if (m == 0) return mint(0);
    if (m + m > n + 1) return POW[n] - query(n, n + 1 - m);
    --m;
    int a = m / B;

    if (m <= a * B + B / 2) {
      u128 t = 0;
      FOR(i, a * B + 1, m + 1) {
        t += u64(fact_inv<mint>(i).val) * (fact_inv<mint>(n - i).val);
      }
      return _get(n, a) + mint::raw(t % mod) * fact<mint>(n);
    } else {
      u128 t = 0;
      FOR(i, m + 1, (a + 1) * B + 1) {
        t += u64(fact_inv<mint>(i).val) * (fact_inv<mint>(n - i).val);
      }
      return _get(n, a + 1) - mint::raw(t % mod) * fact<mint>(n);
    }
    return 0;
  }

 private:
  mint _get(int n, int k) {
    if (n <= k * B) return POW[n];
    return dat[k][n - k * B] * fact_inv<mint>(k * B);
  }
};

template <typename mint>
struct Prefix_Sum_Of_Binom_Offline {
  vc<pair<int, int>> query;

  void add(int n, int m) { query.eb(n, m); }

  vc<mint> calc() {
    int Q = len(query);
    vc<mint> ANS(Q);
    auto I = Mo::get_mo_order(query);
    int n = 0, m = 0;
    mint ans = 0;
    mint inv2 = inv<mint>(2);
    for (auto& i : I) {
      auto [nn, mm] = query[i];
      while (n < nn) {
        ans = ans + ans - C<mint>(n, m - 1);
        n++;
      }
      while (n > nn) {
        ans += C<mint>(n - 1, m - 1);
        ans *= inv2;
        --n;
      }
      while (m < mm) {
        ans += C<mint>(n, m++);
      }
      while (m > mm) {
        ans -= C<mint>(n, --m);
      }
      ANS[i] = ans;
    }
    return ANS;
  }
};
Back to top page