题意很简单啦，求S(n,m)的值
通过打表我们可以知道
S(n + 1, m) = S(n, m) * 2 - C(n, m);
S(n - 1, m) = (S(n, m) + C(n - 1, m)) / 2;
首先我们考虑杨辉三角和二项式定理，但是看了看数据情况，貌似时间不允许呢
这个时候就要祭出莫队算法啦，关于莫队算法呢，更详细的理解请看：2010国家集训队《小Z的袜子》命题报告
莫队算法是一种用于解决可离线的，求区间[L,R]问题的算法
这个题当然就可以离线去求啦，莫队算法在解决离线区间询问几乎是无敌的（分块大法好），复杂度在O(n^3/2)左右
那这个题也妥妥的稳过了
这个题由于在处理阶乘的时候会出现被取余的情况，所以在计算C(L,R)进行除运算阶乘时，计算会不正确，这时候就需要用到费马小定理去计算逆元啦
费马小定理：假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。
Problem B. Harvest of Apples
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 3313 Accepted Submission(s): 1284
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.
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).
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
#include <iostream>
#include <cmath>
#include <algorithm> using namespace std; const int maxn = 1e5 + ;
const int mod = 1e9 + ;
const int MAX = 1e5;
int pos[maxn];
long long ans[maxn];
long long jx[maxn];
long long jxny[maxn]; struct node
{
int l, r;
int id;
bool operator < (node a) const
{
if (pos[id] == pos[a.id])
return r < a.r;
return pos[id] < pos[a.id];
}
}q[maxn]; long long quick_mod(long long n, long long m)
{
long long ret = ;
while (m>) {
if (m & ) ret = ret * n%mod;
n = n * n%mod;
m >>= ;
}
return ret;
}//快速幂 void init() {
jx[] = ;
for (int i = ; i <= MAX; i++) {
jx[i] = (jx[i - ] * i) % mod;
}
jxny[MAX] = quick_mod(jx[MAX], mod - );
for (int i = MAX - ; i >= ; i--) {
jxny[i] = jxny[i + ] * (i + ) % mod;
}
}//预处理阶乘和逆元 long long get(int l, int r)
{
if (r > l)
return ;
return jx[l] * jxny[r] % mod * jxny[l - r] % mod;
} int main()
{
init();
ios::sync_with_stdio(false);
int t;
cin >> t;
int sq = sqrt();
for (int i = ; i < t; i++)
{
cin >> q[i].l >> q[i].r;
q[i].id = i;
pos[i] = q[i].l / sq;
} sort(q,q+t); int l = , r = ;
long long num = ;
for (int i = ; i < t; i++)
{
while (l < q[i].l)
{
num = (num * + mod - get(l,r)) % mod;
l++;
}
while (l > q[i].l)
{
l--;
num = (num + get(l, r)) * quick_mod(, mod - ) % mod;
}
while (r < q[i].r)
{
r++;
num = (num + get(l, r) + mod) % mod;
}
while (r > q[i].r)
{
num = (num - get(l, r) + mod) % mod;
r--;
}
ans[q[i].id] = num;
} for (int i = ; i < t; i++)
cout << ans[i] << endl; return ;
}