题目描述

        There are $n$ apples on a tree, numbered from $1$ to $n$.
        Count the number of ways to pick at most $m$ apples.

输入输出格式

输入格式

        The first line of the input contains an integer $T (1≤T≤10^5)$ denoting the number of test cases.
        Each test case consists of one line with two integers $n,m (1≤m≤n≤10^5)$.

输出格式

        For each test case, print an integer representing the number of ways modulo $10^9+7$.

输入输出样例

Sample input

2
5 2
1000 500

Sample ouput

16
924129523

题解

        莫队算法神题。
        就是求：

        复杂度$O(Tn)$，会T，考虑将要求的数写成$S(n,m)$的形式：

        立即可以推知：

        另外注意到：

        于是可得：

        将区间$[0,10^5]$分块处理，$n$看成区间左端点，$m$看成区间右端点，根据上面的递推式进行更新，跑一遍莫队算法即可，复杂度在$O(T\sqrt n)$。
        注意移动指针时可能出现$m>n$的情况，这样的时候组合数直接就是0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

using namespace std;
int fac[100005], inv[100005], t, l, r, now, belong[100005];
const int MOD = static_cast<const int>(1e9 + 7);

struct Node {
    int n, m;
    int ans, rk;

    bool operator<(Node s) {
        if (belong[n] == belong[s.n])return belong[m] < belong[s.m];
        return belong[n] < belong[s.n];
    }
} node[100005];

inline int C(int n, int m) {
    if (n < 0 || m < 0)return 0;//注意这里的判断
    if (m > n)return 0;
    return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

int qPow(int x, int y) {
    int ans = 1, sta = x;
    while (y) {
        if (y & 1)ans = 1ll * ans * sta % MOD;
        sta = 1ll * sta * sta % MOD, y >>= 1;
    }
    return ans;
}

bool cmp(Node a, Node b) {
    return a.rk < b.rk;
}

int main() {
    ios::sync_with_stdio(false);
    fac[0] = 1, inv[0] = 1;
    for (int i = 1; i <= 100000; i++)fac[i] = 1ll * fac[i - 1] * i % MOD;//预处理阶乘以及逆元
    for (int i = 1; i <= 100000; i++)inv[i] = qPow(fac[i], MOD - 2);
    cin >> t;
    for (int i = 1; i <= t; i++)cin >> node[i].n >> node[i].m, node[i].rk = i;
    int base = static_cast<int>(sqrt(100000));
    for (int i = 0; i <= 100000; i++)belong[i] = i / base + 1;//分块
    sort(node + 1, node + t + 1);
    l = 1, r = 0, now = 1;//C(1,0)=1
    for (int i = 1; i <= t; i++) {
        while (l > node[i].n)now = 1ll * (1ll * now + C(l - 1, r)) % MOD * inv[2] % MOD, --l;//移动指针的过程
        while (l < node[i].n)now = 1ll * (2ll * now - C(l, r)) % MOD, ++l;
        while (r > node[i].m)now = (now - C(l, r)) % MOD, --r;
        while (r < node[i].m)now = (now + C(l, r + 1)) % MOD, ++r;
        node[i].ans = now;
    }
    sort(node + 1, node + t + 1, cmp);
    for (int i = 1; i <= t; i++)cout << (node[i].ans + MOD) % MOD << endl;
    return 0;
}