hdu 6333

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

chendu | We have carefully selected several similar problems for you: 6343 6342 6341 6340 6339

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <vector>
 5 #include <cmath>
 6 #include <algorithm>
 7 using namespace std;
 8 #define N 100005//一开始是10005,超时
 9 #define mod 1000000007
10 #define gep(i,a,b) for(int i=a;i<=b;i++)
11 #define mem(a,b) memset(a,b,sizeof(a))
12 #define ll  long long 
13 ll fac[N]={1,1},inv[N]={1,1},f[N]={1,1};
14 ll c(ll a,ll b)
15 {
16    if(b>a)  return 0;
17    return fac[a]*inv[b]%mod*inv[a-b]%mod;
18 }
19 void init()
20 {
21     gep(i,2,N-1){
22         fac[i]=fac[i-1]*i%mod;
23         f[i]=(mod-mod/i)*f[mod%i]%mod;
24         inv[i]=inv[i-1]*f[i]%mod;
25     }
26 }
27 struct Ma{
28     ll n,m;
29     int id;
30     bool operator <(const Ma&a)const{
31         return n<a.n;//排序
32     }
33 }ma[N];
34 vector<Ma>ve[N];
35 ll ans[N];
36 int t;
37 int main()
38 {
39   init();  
40   scanf("%d",&t);
41   ll mx=sqrt(100000);
42   gep(i,1,t){
43      scanf("%lld%lld",&ma[i].n,&ma[i].m);
44      ll x=ma[i].m/mx;
45       ma[i].id=i;
46      ve[x].push_back(ma[i]);//分块
47   } 
48   gep(i,0,mx){
49       if(!ve[i].size())  continue;
50       sort(ve[i].begin(),ve[i].end());//排序
51       int k=ve[i].size();
52       ll val=0,ik=-1,mn=ve[i][0].n;//一次处理每组数据
53       /*
54       s(n,m):c(n,0)+c(n,1)+……c(n,m)
55       s(n,m)=2*s(n-1,m)-c(n-1,m)
56       */
57       gep(j,0,k-1){
58           while(mn<ve[i][j].n) val=(2ll*val+mod-c(mn++,ik))%mod;//+mod
59           while(ik<ve[i][j].m) val=(val+c(mn,++ik))%mod;//,++ik,不是ik++,可以不加mod
60           while(ik>ve[i][j].m) val=(val+mod-c(mn,ik--))%mod;//+mod
61           ans[ve[i][j].id]=val;
62       }  
63   }
64   gep(i,1,t){
65        printf("%lld
",ans[i]);
66       }      
67   return 0;
68 }