问题 B: Harvest of Apples

时间限制: 1 Sec  内存限制: 128 MB

提交: 78  解决: 35

[] [] [] [命题人:]

题目描述

There are n apples on a tree, numbered from 1 to n.

Count the number of ways to pick at most m apples.

 

输入

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

 

输出

For each test case, print an integer representing the number of ways modulo 109+7.

 

样例输入

25 21000 500

 

样例输出

16924129523

 

[][]

官方题解

重点就是划出来的公式，然后套莫队即可

代码：

#include 
    
     using namespace std;const  int maxn=1e5+100;#define INF 0x3f3f3f;const int mod=1e9+7;typedef long long ll;struct node{    ll n,m;    int p;}s[maxn];ll block;ll fac[maxn],inv[maxn];ll ans[maxn];ll noww;ll qpow(ll x,ll y){    ll ret = 1;    while(y){        if(y&1) ret = ret * x % mod;        x = x * x % mod;        y >>= 1;    }    return ret;}void init(){    fac[0] = 1;    for(int i=1; i
     
      =0; i--) inv[i] = inv[i+1] * (i+1) % mod;}ll C(ll x,ll y){    return fac[x] * inv[y] %mod * inv[x-y] % mod;}bool cmp(node x,node y){    if(x.n / block == y.n / block)  return x.m < y.m;    return x.n / block < y.n / block;}int main(){    int t;    scanf("%d",&t);    block = sqrt(maxn);    init();    for(int i=0; i
      
        s[i].n){            noww = (noww + C(l-1,r)) % mod * inv[2] % mod;            l--;        }        while(r < s[i].m){            r++;            noww = (noww + C(l,r)) % mod;        }        while(r > s[i].m){            noww = (noww + mod - C(l,r)) % mod;            r--;        }        ans[s[i].p] = noww;    }    for(int i=0; i
      
     
    

刚刚学了莫队，赶紧把原来两个莫队给补了