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

Problem B. Harvest of Apples

Problem Description

There are

Input

The first line of the input contains an integer

Output

For each test case, print an integer representing the number of ways modulo

Sample Input

2 5 2 1000 500

Sample Output

16 924129523

Source

2018 Multi-University Training Contest 4

题解：

 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 }