hdu-6333-莫队

Problem B. Harvest of Apples

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2970 Accepted Submission(s): 1153

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

　　经过观察可以发现，设S(m,n)=C(0,n)+C(1,n)+.....+C(m,n)的话，S(m,n+1)=2*S(m,n)-C(m,n) , S(m,n-1)=(S(m,n)+C(m,n-1))/2。

　　S(m-1,n)=S(m,n)-C(m,n) ,S(m+1,n)=S(m,n)+C(m+1,n),也就是说我们能在O(1)求出来这四个式子，这样就可以用莫队处理了。

分块的时候我错把 q[i].m/M写成了 i/M导致一直T ，是对mi所在的块作为关键字而不是输入的次序。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long 
 4 #define eps 1e-6
 5 #define mod 1000000007
 6 //LL mod=1e9+7;
 7 const int maxn=100000+5;
 8 LL len,p[maxn]={1,1},inv[maxn]={0,1},p_inv[maxn]={1,1},ans[maxn];
 9 int t;
10 struct Query{
11     LL n,m,blo;
12     int id;
13     bool operator<(const Query&C)const{
14         if(blo==C.blo) return n<C.n;
15         return blo<C.blo;    
16     }
17 }q[maxn];
18 LL cal(LL a,LL b)  
19 {
20     if(b>a)
21         return 0;
22     return p[a]*p_inv[b]%mod*p_inv[a-b]%mod;
23 }
24 int main(){
25     int n,m,i,j,k;
26     len=sqrt(maxn);
27     for(i=2;i<=100000;++i){
28     p[i]=p[i-1]*i%mod;
29     inv[i]=(mod-mod/i)*inv[mod%i]%mod;
30     p_inv[i]=p_inv[i-1]*inv[i]%mod;
31     }
32     scanf("%d",&t);
33     for(i=1;i<=t;++i){
34         scanf("%lld %lld",&q[i].n,&q[i].m);
35         q[i].id=i;
36         q[i].blo=q[i].m/len;
37     }
38     sort(q+1,q+1+t);
39     int L=0,R=1;
40     LL res=1;
41     for(i=1;i<=t;++i){
42         while(L<q[i].m){
43             res=(res+cal(R,++L))%mod;
44         }
45         while(L>q[i].m){
46             res=(res+mod-cal(R,L--))%mod;
47         }
48         while(R<q[i].n){
49             res=(res*2+mod-cal(R++,L))%mod;
50         }
51         while(R>q[i].n){
52             res=(res+cal(--R,L))%mod*inv[2]%mod;
53         }
54         ans[q[i].id]=res;
55     }
56     for(i=1;i<=t;++i)printf("%lld
",ans[i]);
57     return 0;
58 }