牛客IOI周赛18-提高组 C-山脉 题解

考虑枚举山峰的最右边位置 ，那么 ~ 是一个不下降序列， ~ 也是个不下降序列。

考虑一个最大高度为 的不下降序列的方案数，做一下差分，那么有若干个位置不为 ，且这些位置的总和为 ，那么相当于将 分给这 个位置，由于数字都大于 ，所以第一个位置的差分值至少为 ，所以实际上是将 分给 个位置，方案数就是个插板法 。

答案就是：

后面那个部分是求杨辉三角一列的和，套公式得到：

改一下：

考虑化简里面的部分，其实里面就是在求：

这有点像一个卷积的形式，考虑生成函数，设 。

那么上面那个式子求出来的，其实就是 卷 的第 项系数，即

所以 ，代入到上面的式子，得到：，这个就是答案了。

代码如下：

#include <cstdio>
#define maxn 15000010
#define mod 1000000007

int T,n,m;
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
int fac[maxn],inv_fac[maxn];
void work(){
    fac[0]=inv_fac[0]=1;
    for(int i=1;i<=maxn-10;i++)fac[i]=1ll*fac[i-1]*i%mod;
    inv_fac[maxn-10]=ksm(fac[maxn-10],mod-2);
    for(int i=maxn-11;i>=1;i--)inv_fac[i]=1ll*inv_fac[i+1]*(i+1)%mod;
}
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
int C(int x,int y){
    if(x<y)return 0;
    return 1ll*fac[x]*inv_fac[y]%mod*inv_fac[x-y]%mod;
}

int main()
{
    work();
    scanf("%d",&T);while(T--)
    {
        scanf("%d %d",&m,&n);int ans=0;
        for(int i=1;i<=m;i++)add(ans,C(n+2*i-3,n-1));
        printf("%d\n",ans);
    }
}