时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
n个不同的滑稽果中，每个滑稽果可取可不取，从所有方案数中选取一种，求选取的方案中滑稽果个数不超过m的概率。(对109+7取模)
输入描述:
第一行一个正整数T( T <= 10^5 )随后T行每行两个整数n,m ( 0 < m <= n <= 10^5 )
输出描述:
T行，每行一个整数表示答案。
输入描述:
第一行一个正整数T( T <= 10^5 )随后T行每行两个整数n,m ( 0 < m <= n <= 10^5 )
输出描述:
T行，每行一个整数表示答案。
示例1
输入
复制
复制
2
5 2
5 1
5 2
5 1
输出
复制
复制
500000004
687500005
687500005
解题思路：很明显总方案数为2种，而合法的方案数为C(n,0)+C(n,1)+……+C(n,m)种
因为有t组询问，如果每次暴力求，必然超时。
我们令S(n,m)=C(n,0)+C(n,1)+……+C(n,m),答案就是S(n,m)/2
既然暴力超时，我们考虑离线的做法，我们会很自然想到莫队，但是要用莫队，我们必须要满足在在O(1)的时间下得到[L,R-1]和[L,R+1]和[L-1,R]和[L+1,R]的答案.
首先来看m的变化，很简单S(n,m)=S (n,m-1)+C(n,m)
然后来看n的变化，由于C(a,b)=C(a-1,b)+C(a-1,b-1),所以我们可以得到S(n,m)=2S(n-1,m)-C(n-1,m)
然后直接上莫队就好了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+;
const int N=1e5+;
int n,m,pos[N];
long long re[N],inv[N],fac[N];
struct node{
int l,r,id;
}Q[N];
ll Ans=,ans[N];
int L=,R=;
ll qpow(ll a,ll b){
ll res=;
while(b){
if(b&) res=res*a%mod;
b>>=;
a=a*a%mod;
}
return res;
}
bool cmp(node x,node y){
if(pos[x.l]==pos[y.l]) return pos[x.r]<pos[y.r];
return pos[x.l]<pos[y.l];
}
void init(int n){
re[] = inv[] = fac[] = ;
for(int i = ;i <= n;++i) fac[i] = fac[i-] * i % mod;
for(int i = ;i <= n;++i) inv[i] = (mod-mod/i)*inv[mod%i] % mod;
for(int i = ;i <= n;++i) re[i] = re[i-] * inv[i] % mod;
}
long long C(int a,int b){
if(a < ||b>a) return ;
return fac[a]*re[b]%mod*re[a-b]%mod;
}
void addL(int l,int r){
Ans=(Ans+C(r,l))%mod;
}
void delL(int l,int r){
Ans=(Ans-C(r,l)+mod)%mod;
}
void addR(int l,int r){
Ans=(*Ans-C(r-,l)+mod)%mod;
}
void delR(int l,int r){
Ans=(Ans+C(r-,l))%mod*inv[]%mod;
}
int main(){
init();
int t;
scanf("%d",&t);
int sz=sqrt();
for(int i=;i<=;i++) pos[i]=(i-)/sz+;
for(int i=;i<=t;i++){
scanf("%d%d",&Q[i].r,&Q[i].l);
Q[i].id=i;
}
sort(Q+,Q+t+,cmp);
for(int i=;i<=t;i++){
while(L<Q[i].l){
L++;
addL(L,R);
}
while(L>Q[i].l){
delL(L,R);
L--;
}
while(R<Q[i].r){
R++;
addR(L,R);
}
while(R>Q[i].r){
delR(L,R);
R--;
}
ans[Q[i].id]=Ans*qpow(qpow(,R),mod-)%mod;
}
for(int i=;i<=t;i++)
printf("%lld\n",ans[i]);
return ;
}