分块求组合数区间和的方法

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)$

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();
}