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

Recommend

这题刚写的时候公式及其的容易推 C(n,0)+C(n,1)+C(n,2)+。。。+C(n,m)

然后一直在想能不能化简这一项一项的求复杂度会爆炸的

最后的题解是莫队

C(n,m)=C(n-1,m-1)+C(n-1,m)

设 S(n,m)=C(n,0)+C(n,1)+C(n,2)+。。。+C(n,m)

然后将S(n,m) 通过第一个公式拆项

最后化简变为 S(n,m)=2*S(n-1,m)-C(n-1,m);

预处理阶乘逆元然后就 OK了

莫队大法好

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <iostream>
 8 #include <map>
 9 #include <stack>
10 #include <string>
11 #include <vector>
12 #define  pi acos(-1.0)
13 #define  eps 1e-6
14 #define  fi first
15 #define  se second
16 #define  lson l,m,rt<<1
17 #define  rson m+1,r,rt<<1|1
18 #define  bug         printf("******
")
19 #define  mem(a,b)    memset(a,b,sizeof(a))
20 #define  fuck(x)     cout<<"["<<x<<"]"<<endl
21 #define  f(a)        a*a
22 #define  sf(n)       scanf("%d", &n)
23 #define  sff(a,b)    scanf("%d %d", &a, &b)
24 #define  sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
25 #define  sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
26 #define  pf          printf
27 #define  FRE(i,a,b)  for(i = a; i <= b; i++)
28 #define  FREE(i,a,b) for(i = a; i >= b; i--)
29 #define  FRL(i,a,b)  for(i = a; i < b; i++)
30 #define  FRLL(i,a,b) for(i = a; i > b; i--)
31 #define  FIN         freopen("DATA.txt","r",stdin)
32 #define  gcd(a,b)    __gcd(a,b)
33 #define  lowbit(x)   x&-x
34 #pragma  comment (linker,"/STACK:102400000,102400000")
35 using namespace std;
36 typedef long long  LL;
37 typedef unsigned long long ULL;
38 const int INF = 0x7fffffff;
39 const int mod = 1e9 + 7;
40 const int maxn = 1e5 + 10;
41 int t, sz;
42 LL inv[maxn], a[maxn], b[maxn];
43 struct node {
44     int l, r, id;
45     LL ans = 0;
46 } qu[maxn];
47 int cmp(node a, node b) {
48     return a.l / sz == b.l / sz ? a.r < b.r : a.l < b.l;
49 }
50 LL expmod(LL a, LL b) {
51     LL ans = 1;
52     while(b) {
53         if (b & 1) ans = ans * a % mod;
54         a = a * a % mod;
55         b = b >> 1;
56     }
57     return ans;
58 }
59 void init() {
60     a[1] = 1;
61     for (int i = 2 ; i < maxn ; i++) a[i] = a[i - 1] * i % mod;
62     for (int i = 1 ; i < maxn ; i++) b[i] = expmod(a[i], mod - 2);
63 }
64 LL C(int n, int m) {
65     if (m > n || n < 0 || m < 0 ) return 0;
66     if (m == n || m == 0) return 1;
67     return a[n] * b[m] % mod * b[n - m] % mod;
68 }
69 
70 int main() {
71     init();
72     sf(t);
73     for (int i = 1 ; i <= t ; i++) {
74         sff(qu[i].l, qu[i].r);
75         qu[i].id = i, qu[i].ans = 0;
76     }
77     sz = sqrt(maxn);
78     sort(qu + 1, qu + 1 + t, cmp);
79     LL sum = 1;
80     for (int i = 1, L = 1, R = 0 ; i <= t ; i++) {
81         while(L < qu[i].l) sum = (2 * sum - C(L++, R) + mod) % mod;
82         while(L > qu[i].l) sum = ((sum + C(--L, R)) * b[2]) % mod;
83         while(R < qu[i].r) sum = (sum + C(L, ++R)) % mod;
84         while(R > qu[i].r) sum = (sum - C(L, R--) + mod) % mod;
85         qu[qu[i].id].ans = sum;
86     }
87     for (int i = 1 ; i <= t ; i++) printf("%lld
", qu[i].ans);
88     return 0;
89 }