Problem B. Harvest of Apples

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 1006    Accepted Submission(s): 381

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次询问，求C(n,0)+C(n,1)+...C(n,m)

思路

通过暴力打表 100000x100000 这样会超时 ，因为C(n,m)=C(n-1,m-1)+C(n-1,m),所以sum[n][m]=2*sum[n-1][m]-C(n-1,m)

这样就可以通过某个点求出其他点的值，用分块，每200x200的矩阵压成一个点，这样就可以快速查询。

#include
     
      #include
      
       #include
       
        using namespace std;const int mod=1e9+7;typedef long long ll;int len=200;ll A[100005],p[100005],q[100005];ll dp[505][505];ll qpow(ll a,ll b,ll c){    ll ans=1;    while(b)    {        if(b&1)            ans=ans*a%c;        a=a*a%c;        b>>=1;    }    return ans;}ll C(int n,int m){    return  (A[n]*p[m])%mod*p[n-m]%mod;}void init(){    ll sum;    for(int i=0;i<=500;i++)    {        int m=i*len;        sum=0;        for(int j=0;j<=m;j++)        {            sum+=C(m,j);            sum%=mod;            if(j%len==0)            {                dp[i][j/len]=sum;            }        }    }}ll get(int n,int m){    int x,y;    x=n/len*len;    y=m/len*len;    ll ans;    ans=dp[n/len][m/len];    for(int i=x;i