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.
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).
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
題目大概:
給出T組資料,每組資料一個n 和一個 m,計算C(n,0)+C(n,1)+.....+C(n,m),%1e9+7。
思路:
剛開始很容易想到分塊,發現是離線詢問,指針的跳動也可以O(1)實作,那麼就可以用莫隊解決。
這是楊輝三角,楊輝三角的字首和,可以推出前一項和後一項的關系,畢竟是字首和,比較容易推。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+100;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
int fac[maxn],inv[maxn],be[maxn],ans[maxn];
int inv2;
struct poin
{
int n,m,id;
} G[maxn];
bool cmp(const poin &a,const poin &b)
{
if(be[a.n]==be[b.n])return a.m<b.m;
else return a.n<b.n;
}
long long pow_mod(long long a,long long b,long long m)
{
a=a%m;
long long ans=1;
while(b)
{
if(b&1)
{
ans=(ans*a)%m;
b--;
}
b>>=1;
a=a*a%m;
}
return ans;
}
ll C(int n,int m)
{
return (1LL*fac[n]*inv[m]%mod*inv[n-m])%mod;
}
void init()
{
int mx=100000;
fac[0]=1;
for(int i=1; i<=mx; i++)
{
fac[i]=(1LL*fac[i-1]*i)%mod;
}
inv2=pow_mod(2,mod-2,mod);
inv[mx]=pow_mod(fac[mx],mod-2,mod);
for(int i=mx-1; ~i; i--)inv[i]=(1LL*inv[i+1]*(i+1))%mod;
int block=sqrt(mx);
for(int i=1; i<=mx; i++)
{
be[i]=i/block;
}
}
int main()
{
int T;
init();
scanf("%d",&T);
for(int i=1; i<=T; i++)
{
scanf("%d%d",&G[i].n,&G[i].m);
G[i].id=i;
}
sort(G+1,G+1+T,cmp);
int n=1,m=1;
int sum=2;
for(int i=1; i<=T; i++)
{
while(n<G[i].n)sum=( 0LL + 2*sum + mod - C(n++,m)) % mod;
while(n>G[i].n)sum= ( sum + C(--n, m)) % mod * inv2 % mod;
while(m<G[i].m) sum =(sum + C(n, ++m )) % mod;
while(m>G[i].m)sum =(sum + mod - C(n, m-- )) % mod;
ans[G[i].id]=sum;
}
for(int i=1;i<=T;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}