hyz's blog
0%

2018杭电多校第四场B题 Harvest of Apples

发表于

题意

有n个苹果，编号为1到n，求从中最多选取m个苹果的方案数。
测试组数有T组。($$ 1≤T≤10^5, 1≤m≤n≤10^5 $$)

分析

官方题解:
定义 $$ S(n, m) = \sum_{i = 0} ^ {m} {n \choose i} $$，不难发现$$ S(n,m)=S(n,m−1)+{n \choose m} $$, $$ S(n,m)=2S(n−1,m)−{n-1 \choose m} $$.
也就是说，如果我们知道 S(n, m)，就能以 O(1) 的代价计算出S(n−1,m), S(n,m−1), S(n+1,m), S(n,m+1)，可以采用莫队算法。

水题，直接实现就行了。

代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const double Eps=1e-7;

const int p = 1e9 + 7;
ll fac[N], ni[N], ans, an[N], ni2;
int len, n, m, T;

ll pow_mod(ll a, ll b, ll p) {    //辅助函数
    ll ret = 1;
    while(b) {
        if(b & 1) ret = (ret * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ret;
}

ll inv_Fermat(ll a, ll p) {            //费马小定理求a关于p的逆元 
    return pow_mod(a, p-2, p);
}

void init() {
    fac[0] = 1;
    len = sqrt(100000);
    ni2 = inv_Fermat(2, p);
    for(int i = 1; i <= 100005; i++)
        fac[i] = fac[i-1] * i % p;
    ni[100005] = inv_Fermat(fac[100005], p);
    for(int i = 100004; i >= 0; i--)
        ni[i] = ni[i+1] * (i + 1) % p;
}

struct Node {
    int n, m, block, id;
    Node() {}
    Node(int n, int m, int id):n(n), m(m), id(id) {
        block = n / len;
    }
    bool operator < (Node &rhs) const {
        if(block == rhs.block) return m < rhs.m;
        return block < rhs.block;
    }
}q[N];

ll C(int n, int m) {
    return fac[n] * ni[m] % p * ni[n-m] % p;
}

int main(void) {
    init();

    scanf("%d", &T);
    for(int i = 0; i < T; i++) {
        scanf("%d%d", &n, &m);
        q[i]= Node{n, m, i};
    }
    sort(q, q + T);
    n = 1, m = 1;
    ans = 2;
    for(int i = 0; i < T; i++) {
        Node &t = q[i];
        while(n < t.n) {
            ++n;
            (ans = ans * 2 - C(n-1, m)) %= p;
        }
        while(m < t.m) {
            ++m;
            (ans = ans + C(n, m)) %= p;
        }
        while(n > t.n) {
            (ans = (ans + C(n-1, m)) * ni2) %= p;
            n--;
        }
        while(m > t.m) {
            (ans = ans - C(n, m)) %= p;
            m--;
        }
        ans = (ans + p) % p;
        an[t.id] = ans;
    }
    for(int i = 0; i < T; i++) {
        printf("%lld\n", an[i]);
    }

    return 0;
}