2018 Multi-University Training Contest 4 B Harvest of Apples 莫队算法 Problem B. Harvest of Apples

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll mod = 1e9+7;
 5 const int N = 1e5+10;
 6 struct mo{
 7     int n, k,id;
 8 }q[N];
 9 ll Be[N], fac[N], inv[N], res[N], unit, t;
10 vector<mo> lst[N];
11 ll pow_mod(ll x, ll n){  
12     ll res=1;  
13     while(n>0){  
14         if(n&1)res=res*x%mod;  
15         x=x*x%mod;  
16         n>>=1;  
17     }  
18     return res;  
19 }
20 bool cmp(mo a, mo b) {
21     return a.n < b.n;
22 }
23 ll C(int a, int b) {
24     return fac[a] * inv[b] % mod * inv[a-b] % mod;
25 }
26 int main() {
27     int mx = 100000; unit = sqrt(mx);
28     fac[0] = 1;for(int i = 1; i <= mx; i ++) fac[i] = fac[i-1] * i %mod, Be[i] = i/unit + 1;
29     inv[mx] = pow_mod(fac[mx], mod-2); for(int i = mx-1; i >= 0; i --) inv[i] = inv[i+1] *(i+1) % mod;
30     scanf("%lld", &t);
31     for(int i = 1; i <= t; i ++) {
32         scanf("%d%d",&q[i].n,&q[i].k), q[i].id = i;
33         lst[Be[q[i].k]].push_back(q[i]);
34     }
35     for(int i = 1; i <= mx; i ++) {
36         if(lst[i].size()) {
37             sort(lst[i].begin(),lst[i].end(), cmp);
38             ll val = 0, in = lst[i][0].n, ik = -1;
39             for(auto e : lst[i]) {
40                 while(in < e.n) val = (val + val + mod - C(in++, ik)) % mod;
41                 while(ik < e.k) val = (val + C(in, ++ik)) % mod;
42                 while(ik > e.k) val = (val + mod - C(in, ik--)) % mod;
43                 res[e.id] = val;                
44             }
45         }
46     }
47     for(int i = 1; i <= t; i ++) printf("%lld
",res[i]);
48     return 0;
49 }