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
题意 求出sigma(C(n,0)-C(n,m))
思考：根据官方题解
我们可以取一些定点，然后每次查询就通过离要查询状态最近的点出发。然后暴力的更新到所需要的状态。
所以如果状态能够线性处理出来的话，这个问题就很好解决了。
因此考虑离线处理。
按照以n为第一关键字 m为第二关键字 排序
思考：如何对于每个 n-1行的前缀和 在能接受的时间代价内求得第n行的前缀和。
定义 T(i,j) 为 sigma(C(i,0)-C(i,j)) 那么 T(i,j)=2*T(i-1,j)-C(i-1,j)
这样，状态的转移也可以线性的完成了。
代码：
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAX=1e5+10;
LL inv[MAX];
LL fac[MAX];
const int MOD=1e9+7;
LL quickpow(LL a,LL b){LL ans=1;while(b){if(b&1){ans=(ans*a)%MOD;}a=(a*a)%MOD;b>>=1;}return ans;
}
void init(){fac[0] = 1;for(LL i=1;i<MAX;i++){fac[i] = i * fac[i-1] % MOD;}inv[MAX - 1] = quickpow(fac[MAX - 1],MOD - 2);for(int i = MAX - 2;i >= 0;i--)inv[i] = inv[i + 1] * (i + 1) % MOD;
}
class Node{
public:int id,n,m;bool operator < (const Node &b) const{if(n==b.n){return m<b.m;}return n<b.n;}
};
LL C(long long n,long long m){if(n<0 || m< 0 ) return 0;if(n<m) return 0;return (fac[n]%MOD*inv[n-m]%MOD*inv[m]%MOD)%MOD;
}
Node node[MAX];
LL pre[MAX];
int nowceng=1;
int tot=1;
void up(){for(int i=1;i<=tot;i++){pre[i]=pre[i]*2ll-C(nowceng,300*(i));pre[i]=(pre[i]+MOD)%MOD;}
}
LL ans[MAX];
int main(){int T;init();scanf("%d",&T);for(int i=0;i<T;i++){scanf("%d %d",&node[i].n,&node[i].m);node[i].id=i;}sort(node,node+T);pre[0]=1;nowceng=1;tot=0;for(int i=0;i<T;i++){while(nowceng<node[i].n){up();nowceng++;}while(node[i].m>tot*300 && (tot+1)*300 <= nowceng){pre[tot+1]=pre[tot];tot++;for(int i=1;i<=300;i++){pre[tot]+=C(nowceng,(tot-1)*300+i);pre[tot]%=MOD;}}int base = node[i].m/300;LL cnt = pre[base];int top = node[i].m%300;for(int i=0;i<top;i++){cnt=(cnt+C(nowceng,base*300+1+i))%MOD;}ans[node[i].id] = cnt ;}for(int i=0;i<T;i++){printf("%lld\n",ans[i]);}return 0;
}官方代码：
#include <bits/stdc++.h>
using namespace std;const int N = 200000;
const int MOD = 1000000007;
struct query
{int n, k, i;
} Q[N];
int T;
vector <query> lst[N];
int cnt, mx, chunk;
int fac[N], inv[N], res[N], in_chunk[N];
int powi(int a, int b)
{int c = 1;for (; b; b >>= 1, a = 1ll * a * a % MOD)if (b & 1) c = 1ll * c * a % MOD;return c;
}
int C(int a, int b)
{return 1ll * fac[a] * inv[b] % MOD * inv[a - b] % MOD;
}
int comp(query a, query b)
{return a.n < b.n;
}
int main()
{mx = 100000;fac[0] = 1; for (int i = 1; i <= mx; ++ i) fac[i] = 1ll * fac[i - 1] * i % MOD;inv[mx] = powi(fac[mx], MOD - 2); for (int i = mx - 1; ~i; -- i) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;chunk = sqrt(mx);cnt = 1;for (int i = 1; i <= mx; i += chunk, ++ cnt)for (int j = i; j < i + chunk && j <= mx; ++ j)in_chunk[j] = cnt;cnt --;scanf("%d", &T);for (int i = 1; i <= T; ++ i){scanf("%d%d", &Q[i].n, &Q[i].k), Q[i].i = i;lst[in_chunk[Q[i].k]].push_back(Q[i]);}for (int i = 1; i <= cnt; ++ i) if (lst[i].size()){sort(lst[i].begin(), lst[i].end(), comp);int val = 0, in = lst[i][0].n, ik = -1;for (int j = 0; j < lst[i].size(); ++ j){while (in < lst[i][j].n) val = (0ll + val + val + MOD - C(in ++, ik)) % MOD;while (ik < lst[i][j].k) val = (val + C(in, ++ ik)) % MOD;while (ik > lst[i][j].k) val = (val + MOD - C(in, ik --)) % MOD;res[lst[i][j].i] = val;}}for (int i = 1; i <= T; ++ i) printf("%d\n", res[i]);
}