Problem B. Harvest of Apples
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 3088 Accepted Submission(s): 1201
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
Source
Recommend
题意：有n个苹果，从中取出不超过m个苹果的方法数
分析：因为题目中的T最大是10^5，如果我们每输入一次就运算一次时间复杂度很高会超时，所以我们首先将输入离线存入ask数组
如果直接暴力求ask中每个询问的值离线就没有什么用了，我们在这里通过对ask中的询问进行排序做到线性求解
那么怎么排序呢？
考虑通过杨辉三角形我们可以得到的结论：S(n,m) = S(n,m-1)+C(n,m), S(n,m) = 2*S(n-1,m) - C(n-1,m)
通过这个式子我们知道要想计算出S(n,m)得先计算出S(n,m-1)或S(n-1,m)，也就是我们要在计算n时的结果时先得出关于n-1和m-1的结果
因此我们想到了先按n排序再按m排序，因为n取值很大，所以我们考虑将n分块，分块后每个区间的S(n,m)我们可以通过累加C(n,i)(0<=i<=m)得到，在求下个区间时通过 S(n,m) = 2*S(n-1,m) - C(n-1,m)求
AC代码：
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e5+10;
const ll mod = 1e9+7;
const double pi = acos(-1.0);
const double eps = 1e-8;
ll block, a[maxn], b[maxn];
struct node {
ll le, ri, id, ans;
};
node ask[maxn];
bool cmp( node p, node q ) {
if( (p.le-1)/block == (q.le-1)/block ) { //分成block大小的几块，看n属于哪一块，每一块里面按m排序
return p.ri < q.ri;
} else {
return p.le < q.le;
}
}
ll qow( ll a, ll b ) { //快速幂用于求逆元
ll ans = 1;
while(b) {
if( b&1 ) {
ans = ans*a%mod;
}
a = a*a%mod;
b /= 2;
}
return ans;
}
void init() {
a[1] = 1;
for( ll i = 2; i < maxn; i ++ ) { //计算i的阶乘
a[i] = a[i-1]*i%mod;
}
for( ll i = 1; i < maxn; i ++ ) { //计算i的阶乘的逆元
b[i] = qow(a[i],mod-2);
}
}
ll C( ll n, ll m ) { //计算组合数C(n,m)
if( n < 0 || m < 0 || m > n ) {
return 0;
}
if( m == 0 || m == n ) {
return 1;
}
return (a[n]*b[n-m]%mod)*b[m]%mod;
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
init();
ll T, sum = 1;
block = sqrt(maxn); //以sqrt(maxn)大小分成几块
scanf("%lld",&T);
for( ll i = 1; i <= T; i ++ ) { //离线查询
scanf("%lld%lld",&ask[i].le,&ask[i].ri);
ask[i].id = i;
}
sort(ask+1,ask+T+1,cmp); //按照cmp排序从小到大可以线性计算结果，节省时间
for( ll i = 1, le = 1, ri = 0; i <= T; i ++ ) {
while( le < ask[i].le ) { //S(n,m)=2S(n-1,m)-C(n-1,m)
sum = (2*sum-C(le++,ri)+mod)%mod;
}
while( le > ask[i].le ) { //S(n,m)=(S(n+1,m)+C(n,m))/2
sum = ((sum+C(--le,ri))*b[2])%mod;
}
while( ri < ask[i].ri ) { //S(n,m)=S(n,m-1)+C(n,m)
sum = (sum+C(le,++ri))%mod;
}
while( ri > ask[i].ri ) { //S(n,m)=S(n,m+1)-C(n,m)
sum = (sum-C(le,ri--)+mod)%mod;
}
ask[ask[i].id].ans = sum; //按标号顺序存放结果，只利用了ans，这样不会对后面有的计算造成影响
}
for( ll i = 1; i <= T; i ++ ) {
printf("%lld
",ask[i].ans);
}
return 0;
}