Problem Description
There are n apples on a tree, numbered from 1 to n.
Count the number of ways to pick at most m apples.
Count the number of ways to pick at most m apples.
Input
The first line of the input contains an integer T (1≤T≤105) denoting the number of test cases.
Each test case consists of one line with two integers n,m (1≤m≤n≤105).
Each test case consists of one line with two integers n,m (1≤m≤n≤105).
Output
For each test case, print an integer representing the number of ways modulo 109+7.
Sample Input
2
5 2
1000 500
Sample Output
16
924129523
Source
Recommend
莫队，O(1)转移为：f(n,m+1)=f(n,m)+C(n,m+1)
f(n+1,m)=2f(n,m)-C(n,m).
#include <bits/stdc++.h>
#define maxn 100505
using namespace std;
typedef long long ll;
const ll mod =1e9+7;
struct node
{
ll l,r,pos;
}query[maxn];
ll block;
ll fact[maxn],inv[maxn];
ll Pow(ll x,ll n){
ll ans=1,base=x;
while(n){
if(n&1) ans=ans*base%mod;
base=base*base%mod;
n>>=1;
}
return ans;
}
void init(){
fact[0]=1;
for (int i = 1; i < maxn; ++i)
{
fact[i]=fact[i-1]*i%mod;
}
inv[maxn-1]=Pow(fact[maxn-1],mod-2);
for (int i = maxn-2; i >= 0; --i)
{
inv[i]=inv[i+1]*(i+1)%mod;
}
}
ll C(ll n, ll m)
{
if(n==m||m==0)
return 1;
if(m>n) return 0;
return ((long long)fact[n]*inv[m]%mod)*inv[n-m]%mod;
}
bool cmp(node a,node b)
{
if((a.l/block)==(b.l/block))
{
return a.r<b.r;
}
return ((a.l/block)<(b.l/block));
}
ll ans[maxn];
int main()
{
ll t,i;
init();
//cout<<C(6,4)<<endl;
scanf("%lld",&t);
ll maxim=0;
for(i=1;i<=t;i++)
{
scanf("%lld%lld",&query[i].l,&query[i].r);
query[i].pos=i;
maxim=max(maxim,query[i].l);
}
block=sqrt(maxim);
sort(query+1,query+1+t,cmp);
ll le=1,ri=1;
ll now=2;//le=n,ri=m;
for(i=1;i<=t;i++)
{
while(le<query[i].l)
{
now=(2*now-C(le,ri)+mod)%mod;
le++;
}
while(le>query[i].l)
{ le--;
now=((now+C(le,ri))%mod*inv[2]%mod)%mod;
}
while(ri<query[i].r)
{ ri++;
now=(now+C(le,ri))%mod;
}
while(ri>query[i].r)
{
now=(now-C(le,ri)+5*mod)%mod;
ri--;
}
ans[query[i].pos]=now;
}
for(i=1;i<=t;i++)
{
printf("%lld
",ans[i]);
}
return 0;
}