山脉

NC206073. 山脉

描述

牛能来到了 "小荷山"，他发现这里的山脉海拔与坐标存在一个规律。

考虑山脉的每一座山的坐标在一条直线上，我们用数轴来表示山脉的坐标。

这些山脉的海拔大小都在一个范围之内，我们定义海拔最高的山为 "尖" 。

这个特殊的规律可以表示为：对于 “尖” 的左侧山脉，从左到右山脉的海拔大小呈不下降；

对于 “尖” 的右侧山脉，从右到左山脉的海拔大小呈不下降。而对于所有满足此规律的山脉定义为 "神奇风景"。

由于牛牛并未能够来到这片神奇的山脉，他希望知道 "小荷山" 山脉的神奇风景。

然而牛能并不希望牛牛直接领略到 “小荷山” 的神奇风景，他希望在牛牛求出 “小荷山” 有多少种不同的神奇风景后，再告诉牛牛具体的神奇风景。

然而牛牛算不出来，但是他迫切的希望能够领略到 “小荷山” 的神奇风景，于是他将这个任务交由精通 OI 和 "组合数学" 的你来完成。

我们定义两种神奇风景不同，当且仅当存在某一坐标处的山脉海拔大小不同。

形式化地说，现在从[1,n]中选出m个数生成一个序列，求生成序列恰好为 "单峰序列" 的方案数。

我们定义两个序列不相同，当且仅当存在某一相同位置所放置的数不同。

要求解决t组数据。

要求答案对1e9 + 7取模。

输入描述

   共 t+1行 .

   第1行，仅1个数 , t.

   第2行至第t+1行，每行2个数： n，m .

输出描述

   共 t 行 .

   第1行至第 t 行，每行1个数表示方案数对1e9 + 7取模后的结果

示例1

输入:

2
2 3
3 3

输出:

7
22

说明:

当 n = 2,m = 3 时，符合条件的序列有 {1,1,1},{1,1,2},{1,2,1},{1,2,2},{2,1,1},{2,2,1},{2,2,2}，不符合条件的序列有 {2,1,2}，故答案为 7 .

示例2

输入:

4 
26 26 
262 626 
62626 26262 
2626262 2626266

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 337ms, 内存消耗: 117808K, 提交时间: 2020-09-05 19:10:42

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1.5e7+5,P=1e9+7;
int fac[N],ifac[N];
LL qpow(LL x,LL y){LL res=1;for(;y;y>>=1,x=(LL)x*x%P)if(y&1)res=(LL)res*x%P;return res;}
int C(int x,int y){return (LL)fac[x]*ifac[y]%P*ifac[x-y]%P;}
int main(){
	int T;scanf("%d",&T);fac[0]=1;
	for(int i=1;i<N;i++)fac[i]=fac[i-1]*(LL)i%P;
	ifac[N-1]=qpow(fac[N-1],P-2);
	for(int i=N-2;~i;i--)ifac[i]=ifac[i+1]*(LL)(i+1)%P;
	while(T--){
		int n,m,ans=0;scanf("%d%d",&n,&m);m--;
		for(int i=1,j=m;i<=n;i++,j+=2)ans=(ans+C(j,m))%P;
		printf("%d\n",ans);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 777ms, 内存消耗: 235256K, 提交时间: 2020-09-05 22:48:31

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,N=15000005;
typedef long long ll;
int n,m;
ll f[N],invf[N];
ll C(int n,int m)
{
    return f[n]*invf[n-m]%mod*invf[m]%mod;
}
int main()
{
    f[0]=f[1]=invf[0]=invf[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod,invf[i]=(mod-mod/i)*invf[mod%i]%mod;
    for(int i=2;i<N;i++) invf[i]=invf[i]*invf[i-1]%mod;
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        ll ans=1;
        for(int i=1;i<n;i++)
            ans=(ans+C(m+2*i-1,m-1))%mod;
        printf("%lld\n",ans);
    }
}