AT987 高橋君

AT987 高橋君

莫队

---

莫队，考虑如何将 \(\displaystyle\sum_{i=0}^kC_n^i\) 转移到 \(\displaystyle\sum_{i=0}^{k+1}C_n^i,\ \displaystyle\sum_{i=0}^{k-1}C_n^i,\ \displaystyle\sum_{i=0}^kC_{n+1}^i,\ \displaystyle\sum_{i=0}^kC_{n-1}^i\)

令 \(S=\displaystyle\sum_{i=0}^kC_n^i\)

易知 \(\displaystyle\sum_{i=0}^{k+1}C_n^i=S+C_{n}^{k+1},\ \displaystyle\sum_{i=0}^{k-1}C_n^i=S-C_n^k\)

剩下两个转移，可以考虑杨辉三角 \(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)

\(\displaystyle\sum_{i=0}^kC_{n+1}^i=\displaystyle\sum_{i=0}^kC_n^i+\displaystyle\sum_{i=0}^{k-1}C_n^i=2\times S-C_n^k\)

\(\therefore \displaystyle\sum_{i=0}^kC_n^i=\frac{C_n^k+\displaystyle\sum_{i=0}^kC_{n+1}^i}{2}\)

\(\therefore \displaystyle\sum_{i=0}^kC_{n-1}^i=\frac{S+C_{n-1}^k}{2}\)

综上所述

\[\begin{cases}\displaystyle\sum_{i=0}^{k+1}C_n^i=S+C_n^{k+1}\\\displaystyle\sum_{i=0}^{k-1}C_n^i=S-C_n^k\\\displaystyle\sum_{i=0}^kC_{n+1}^i=2\times S-C_n^k\\\displaystyle\sum_{i=0}^kC_{n-1}^i=\frac{S+C_{n-1}^k}{2}\end{cases}
\]

然后就可以愉快地莫队辣

时间复杂度 \(O(n\sqrt n)\)

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10, P = 1e9 + 7;

int n, bl[maxn], ans[maxn];

int inv[maxn], fact[maxn], fact_inv[maxn];

struct Query {

  int l, r, tid;

  bool operator < (const Query& o) const {

    return bl[l] == bl[o.l] ? r > o.r : l < o.l;

  }

} Q[maxn];

int C(int n, int m) {

  return n < m ? 0 : 1ll * fact[n] * fact_inv[m] % P * fact_inv[n - m] % P;

}

int main() {

  scanf("%d", &n);

  for (int i = 1; i <= n; i++) {

    Q[i].tid = i;

    scanf("%d %d", &Q[i].l, &Q[i].r);

  }

  int sz = sqrt(n);

  bl[1] = inv[1] = 1;

  fact[0] = fact[1] = 1;

  fact_inv[0] = fact_inv[1] = 1;

  for (int i = 2; i < 100001; i++) {

    bl[i] = (i - 1) / sz + 1;

    fact[i] = 1ll * i * fact[i - 1] % P;

    inv[i] = 1ll * (P - P / i) * inv[P % i] % P;

    fact_inv[i] = 1ll * inv[i] * fact_inv[i - 1] % P;

  }

  sort(Q + 1, Q + n + 1);

  int l = 0, r = 0; ll cur = 1;

  for (int i = 1; i <= n; i++) {

    while (l < Q[i].l) {

      cur = (cur + cur - C(l++, r) + P) % P;

    }

    while (l > Q[i].l) {

      cur = 500000004 * (cur + C(--l, r)) % P;

    }

    while (r < Q[i].r) cur += C(l, ++r);

    while (r > Q[i].r) cur -= C(l, r--);

    cur = (cur % P + P) % P;

    ans[Q[i].tid] = cur;

  }

  for (int i = 1; i <= n; i++) {

    printf("%d\n", ans[i]);

  }

  return 0;

}