AT_tenka1_2014_final_d
提供不需要莫队的做法。
我们知道组合数 $c_{i,j}=c_{i-1,j-1}+c_{i-1,j}$，考虑分块，考虑区间 $l,r$ 用 $c_{i,l\sim r}$ 表示这一段区间和，则有 $c_{i,l\sim r}=(c_{i-1,l\sim r}-c_{i-1,r})+(c_{i-1,l\sim r}-c_{i-1,l-1})$
考虑这个是怎么得到的呢，你就画一段区间，你去对区间每一个点加上其贡献方便得到。
然后？然后做完了。
取定块长 $B=316$ 即 $\sqrt n$，把读入离线按照 $n$ 排序，再去做。
顺序做 $\text{O}(N \sqrt N)$，每次计算 $\text{O}(\sqrt N)$
总时间复杂度 $\text{O}(T \log T + N \sqrt N + T \sqrt N)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| void __INIT__(long long n);
#include<bits/stdc++.h>
#define reg register
#define rep(i,a,b) for(reg int i=a;i<=b;i++)
#define drep(i,a,b) for(reg int i=a;i>=b;i--)
#define ll long long
#define int long long
using namespace std;
const int N=2000003,mod=1e9+7;
struct R{
int n,k,id;
bool operator < (const R x)const {
return n<x.n;
}
}r[N];
int L[N],R[N],val[N],sz;
ll fac[N+50],inv[N+50];
ll qpow(ll a,ll b){ll ans=1,tmp=a;while(b){if(b&1)ans=ans*tmp%mod;tmp=tmp*tmp%mod;b>>=1;}return ans;}
ll C(ll n,ll m){ return fac[n]*inv[m]%mod*inv[n-m]%mod;}
ll lucas(ll n,ll m){
if(n<mod&&m<mod){
if(n<m)return 0;
return C(n,m);
}
return lucas(n/mod,m/mod)*lucas(n%mod,m%mod)%mod;
}
int B=316,ans[N];
int rev(int x){
return (x-1)/B+1;
}
signed main(){
__INIT__(2000002);
int m;cin>>m;for(int i=1;i<=m;i++){cin>>r[i].n>>r[i].k;r[i].id=i;}
sort(r+1,r+m+1);
int it=1;
for(int i=1;i<=100001;i++){
int now=(i-1)/B+1;
if(!L[now])L[now]=i;
R[now]=i;
sz=max(sz,now);
}
val[0]=1,val[1]=1;
for(int i=1;i<=m;i++){
while(it<r[i].n){
for(int now=1;now<=sz;now++){
val[now]=(val[now]+val[now]-lucas(it,R[now])+lucas(it,L[now]-1)+mod)%mod;
}
it++;
}
int res=1;
int myr=rev(r[i].k);
if(R[myr]!=r[i].k){
for(int j=L[myr];j<=r[i].k;j++)(res+=lucas(it,j))%=mod;
myr--;
}
for(int j=1;j<=myr;j++)(res+=val[j])%=mod;
ans[r[i].id]=res;
}
for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
return 0;
}
void __INIT__(int n){
fac[1]=1,fac[0]=1;
rep(i,2,n)fac[i]=(i*fac[i-1])%mod;
ll res=inv[n]=qpow(fac[n],mod-2);
drep(i,n-1,0)inv[i]=((res*=(i+1))%=mod);
inv[0]=1;
return void();
}
|
