任意门：
Problem B. Harvest of Apples
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 4043 Accepted Submission(s): 1560
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
Source
题意概括：
有 N 个苹果，问最多选 m 个苹果的方案有多少种？
解题思路：
大佬讲的很好了。
https://blog.csdn.net/codeswarrior/article/details/81359075
推出四个公式，算是一道比较裸的莫队了。
Sm−1n=Smn−CmnSnm−1=Snm−Cnm
Sm+1n=Smn+Cm+1nSnm+1=Snm+Cnm+1(或者Smn=Sm−1n+CmnSnm=Snm−1+Cnm)Smn+1=2Smn−CmnSn+1m=2Snm−Cnm
Smn−1=Smn+Cmn−12Sn−1m=Snm+Cn−1m2(或者Smn=Smn+1+Cmn2Snm=Sn+1m+Cnm2)需要注意的点较多：
1、精度问题，注意数据范围
2、为了保证精度，除法需要转换为逆元，预处理逆元的技巧
AC code:
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #define INF 0x3f3f3f3f 10 #define LL long long 11 using namespace std; 12 const LL MOD = 1e9+7; 13 const int MAXN = 1e5+10; 14 LL N, M; 15 LL fac[MAXN], inv[MAXN]; 16 struct Query 17 { 18 int L, R, id, block; 19 bool operator < (const Query &p)const{ 20 if(block == p.block) return R < p.R; 21 return block < p.block; 22 } 23 }Q[MAXN]; 24 LL res, rev2; 25 LL ans[MAXN]; 26 27 LL q_pow(LL a, LL b) 28 { 29 LL pans = 1LL; 30 while(b){ 31 if(b&1) pans = pans*a%MOD; 32 b>>=1LL; 33 a = a*a%MOD; 34 } 35 return pans; 36 } 37 38 LL C(int n, int k) 39 { 40 return fac[n]*inv[k]%MOD*inv[n-k]%MOD; 41 } 42 43 void init() 44 { 45 rev2 = q_pow(2, MOD-2); // 2的逆元 46 fac[0] = fac[1] = 1; 47 for(LL i = 2; i < MAXN; i++){ //预处理阶乘 48 fac[i] = fac[i-1]*i%MOD; 49 } 50 51 inv[MAXN-1] = q_pow(fac[MAXN-1], MOD-2); //逆推预处理阶乘的逆元 52 for(int i = MAXN-2; i >= 0; i--){ 53 inv[i] = inv[i+1]*(i+1)%MOD; 54 } 55 } 56 57 void addN(int posL, int posR) 58 { 59 res = (2*res%MOD-C(posL-1, posR)%MOD + MOD)%MOD; 60 } 61 62 void addM(int posL, int posR) 63 { 64 res = (res+C(posL, posR))%MOD; 65 } 66 67 void delN(int posL, int posR) 68 { 69 res = (res+C(posL-1, posR))%MOD*rev2%MOD; 70 } 71 72 void delM(int posL, int posR) 73 { 74 res = (res - C(posL, posR) + MOD)%MOD; 75 } 76 77 int main() 78 { 79 int T_case; 80 init(); 81 int len = (int)sqrt(MAXN*1.0); 82 scanf("%d", &T_case); 83 for(int i = 1; i <= T_case; i++){ 84 scanf("%d%d", &Q[i].L, &Q[i].R); 85 Q[i].id = i; 86 Q[i].block = Q[i].L/len; 87 } 88 sort(Q+1, Q+1+T_case); 89 res = 2; 90 int curL = 1, curR = 1; 91 for(int i = 1; i <= T_case; i++){ 92 while(curL < Q[i].L) addN(++curL, curR); 93 while(curR < Q[i].R) addM(curL, ++curR); 94 while(curL > Q[i].L) delN(curL--, curR); 95 while(curR > Q[i].R) delM(curL, curR--); 96 ans[Q[i].id] = res; 97 } 98 for(int i = 1; i <= T_case; i++){ 99 printf("%lld\n", ans[i]);100 }101 102 return 0;103 104 }