2018 Multi-University Training Contest 4-B-Harvest of Apples

题目链接：HDU-6336-Harvest of Apples

（一）题面：

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

 

（二）题意：

求给出n和m，求C(n，0)+C(n，1)+...+C(n，m-1)+C(n，m)的值(MOD 1e9+7)。其中C(n，m)为组合数。

 

（三）题解：

对于组合数C(m，n)有：C(n，m)=n!/m!/(n-m)!，由于阶乘和阶乘的逆元都可以预处理出来，故对于C(n，m)的求解我们可以O(1)地求，但是这里要求C(n，0~m)的和，故直接求和的复杂度为O(n)的，再考虑到数据的组数T，故总的复杂为O(n*T)，由于数据的组数T<=1e5，故直接这么做肯定是会TLE的（然而还是这么交了几发）。

我们需要分析更多有用的性质，对于这种题目，很容易想到去找规律推公式，而对于组合数我们很容易去联想到杨辉三角。将原求和式放到杨辉三角中我们可以发现原题要求的值其实就是杨辉三角中第n行的前m个值的和，我们设其为sum(n，m).由杨辉三角构造的方式，我们便不难得出关系式：sum(n，m)=2sum(n-1，m)-C(n-1，m)。

其表示如下：

可以看到我们将第n行最左边的1加到上一行的最左边，那么上一行的前m个数只有最后一个出现了一次，就可以得到上面的式子了，将上面的式子进行进一步变形，我们可以得到下面的式子：

              sum(n-1，m)=[sum(n，m)+C(n-1，m)]*inv[2]%MOD;  //inv[2]为2的逆元

              sum(n+1，m)=[2*sum(n，m)-C(n，m)]%MOD;

同样的我们有：

              sum(n，m-1)=sum(n，m)-C(n，m);

              sum(n，m+1)=sum(n，m)+C(n，m+1)；

也就是说我们由sum(n，m)的可以O(1)地转移得到sum(n-1，m)，sum(n+1，m)，sum(n，m-1)，sum(n，m+1)的值，<然后考虑到每次的询问n，m可以离线处理，我们便可以跑莫队解决了（这里当然不是我想出来的，甚至菜鸡的我之前都只听说过而没有写过莫队，题量和知识点的体现）>。

然而去学习了一下莫队之后呢，发现这个东西还是挺好学的，也比较容易写，就是复杂度感觉起来会比较神奇(O(nsqrt(n)))。网上有很多优秀的学习资源这里就不展开废话了。

然后莫队写完之后呢，发现一直T，然后怒把标程交了一发，T了╰（‵□′）╯(貌似杭电的测评机不太稳定QWQ)，但是题还是要写的啊，于是再想想再怎么优化：考虑到每一行的全部求和值为2^n，故如果m>n/2的话，那么我们可以由2^n-C(n，m+1~n)的值来求C(n，0~m)的值，而2的幂次方可以预处理，这样的话就可以进行一定的优化，然后才过的。然而第二天又交了一发发现时间<300ms（目前最快），一脸懵逼...

 

（四）代码：

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
#define Blocks 333
#define MOD 1000000007
#define FOR(i,a,b) for(int i=a;i<b;i++)
const int maxn=1e5+10;
using namespace std;
LL inv[maxn],fac[maxn],ans[maxn],Pow2[maxn];
LL ksm(LL x,LL y,LL mod){
    LL res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;y>>=1;
    }
    return res;
}
struct Query{
    int L,R,ID,block,flag;
    bool operator < (const Query& n1)const{
        if(block!=n1.block)return block<n1.block;
        return R<n1.R;
    }
}Q[maxn];
LL C(LL n,LL m){return m<0?0:fac[n]*inv[m]%MOD*inv[n-m]%MOD;}
int main(){
    inv[1]=fac[1]=fac[0]=Pow2[0]=1;
    for(int i=2;i<maxn;i++)fac[i]=fac[i-1]*i%MOD;
    for(int i=1;i<maxn;i++)Pow2[i]=Pow2[i-1]*2%MOD;
    inv[100003]=ksm(fac[100003],MOD-2,MOD);
    for(int i=100002;i>=0;i--)inv[i]=inv[i+1]*(i+1)%MOD;
    int T,n,m;
    scanf("%d",&T);
    FOR(i,0,T){
        scanf("%lld%lld",&Q[i].L,&Q[i].R);
        Q[i].flag=0;Q[i].block=Q[i].L/Blocks;Q[i].ID=i;
        if(Q[i].R>Q[i].L/2){Q[i].flag=1;Q[i].R=Q[i].L-Q[i].R-1;}
    }
    sort(Q,Q+T);
    LL l=1,r=1,res=2;
    FOR(i,0,T){
        while(l<Q[i].L){res=(res*2-C(l,r)+MOD)%MOD;l++;}
        while(l>Q[i].L){res=(res+C(l-1,r))*inv[2]%MOD;l--;}
        while(r<Q[i].R){res=(res+C(l,r+1));r++;if(res>=MOD)res-=MOD;}
        while(r>Q[i].R){res=(res-C(l,r)+MOD);r--;if(res>=MOD)res-=MOD;}
        ans[Q[i].ID]=Q[i].flag?(Pow2[Q[i].L]-res+MOD)%MOD:res;
    }
    FOR(i,0,T)printf("%lld\n",ans[i]);
    return 0;
}

 

（五）总结：

涨姿势的题--莫队算法(还推了两个小时公式，蠢哭)

阶乘逆元的处理方式，我本来是求每一个数的逆元再求阶乘

组合数的求法--第一次这么实现（以前只是看过，套过模板2333）