链接：https://ac.nowcoder.com/acm/contest/7225/C
来源：牛客网
题目描述
牛能来到了 “小荷山”，他发现这里的山脉海拔与坐标存在一个规律。
考虑山脉的每一座山的坐标在一条直线上，我们用数轴来表示山脉的坐标。
这些山脉的海拔大小都在一个范围之内，我们定义海拔最高的山为 “尖” 。
这个特殊的规律可以表示为：对于 “尖” 的左侧山脉，从左到右山脉的海拔大小呈不下降；
对于 “尖” 的右侧山脉，从右到左山脉的海拔大小呈不下降。而对于所有满足此规律的山脉定义为 “神奇风景”。
由于牛牛并未能够来到这片神奇的山脉，他希望知道 “小荷山” 山脉的神奇风景。
然而牛能并不希望牛牛直接领略到 “小荷山” 的神奇风景，他希望在牛牛求出 “小荷山” 有多少种不同的神奇风景后，再告诉牛牛具体的神奇风景。
然而牛牛算不出来，但是他迫切的希望能够领略到 “小荷山” 的神奇风景，于是他将这个任务交由精通 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
输出
复制
318836234
471802003
756001620
760321595
备注:
对于 5% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 6,1 ≤ m ≤ 6
对于另外 5% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 5e5 ,m = 2
对于另外 10% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 5e5 ,3 ≤ m ≤ 5
对于另外 20% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 200 ,1 ≤ m ≤ 200
对于另外 10% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 1e3 ,1 ≤ m ≤ 1e3
对于另外 30% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 1e5 ,1 ≤ m ≤ 1e5
对于 100% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 5e6 ,1 ≤ m ≤ 5e6
思路：
首先考虑一个简单的问题，构成长度为n的不递减序列，保证 1 ≤ a [ i ] ≤ m 1≤a[i]≤m 1≤a[i]≤m，求方案数。
这实际上就是把 n n n个相同物品放到 m m m个不同背包里面，且背包可以为空。
是经典的隔板法问题，结果为 C ( n + m − 1 , m − 1 ) C(n+m-1,m-1) C(n+m−1,m−1)
对于题目中的单峰序列，也可以同样考虑，在确定了最大值 i i i以后，在 i i i的左边有 i − 1 i-1 i−1种数， i i i的右边有 i − 1 i-1 i−1种数，所以一共有 2 ∗ i − 1 2*i-1 2∗i−1种数，相当于这么多背包，然后一共 m − 1 m-1 m−1个物品（至少放一个数在 i i i背包里面）。
所以结果为 C ( m − 1 + i ∗ 2 − 2 , i ∗ 2 − 2 ) C(m - 1 + i * 2 - 2,i * 2 - 2) C(m−1+i∗2−2,i∗2−2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
using namespace std;typedef long long ll;
const int maxn = 2e7 + 7;
const int mod = 1e9 + 7;int fac[maxn],inv[maxn];ll qpow(ll x,ll n) {ll res = 1;while(n) {if(n & 1) res = res * x % mod;n >>= 1;x = x * x % mod;}return res;
}void init() {fac[0] = inv[0] = 1;for(int i = 1;i < maxn;i++) {fac[i] = 1ll * fac[i - 1] * i % mod;}inv[maxn - 1] = (int) qpow(fac[maxn - 1],mod - 2);for(int i = maxn - 2;i >= 1;i--) {inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;}
}ll C(ll n,ll m) {if(n < m || m < 0) return 0;return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}int main() {init();int T;scanf("%d",&T);while(T--) {int n,m;scanf("%d%d",&n,&m);ll ans = 0;for(int i = 1;i <= n;i++) {ans = (ans + C(m - 1 + i * 2 - 2,i * 2 - 2)) % mod;}printf("%lld\n",ans);}return 0;
}