TIOJ-1607

發表於 更新於 Disqus：

在寬度為n的照片中，總共有多少種不同的山稜線呢 ?

為了簡化問題，一段長度為n的山稜線將由許多寬度為1的片段構成。
同時在每個片段當中，山稜線不是45度斜向上就是45度斜向下。
當然，相鄰兩個片段的山稜線必須連續，而且山稜線的兩端必須貼齊地平線。
此外，山稜線的任何一部分都不能低於地平線(即照片底端)。

舉例來說，以下就是一個合法的山稜線：

1
2
3
　　　　　　　　／＼　　　　　　　　　　 ／＼
　／＼　　　　／　　＼／＼　　／＼／＼／　   ＼
／　　＼／＼／　　　　　　＼／　　　　　　　   ＼

因為答案可能很大，所以你只要輸出山稜線數量除以1,000,000,007的餘數即可。
T筆測資，
$n\le 10^6, T\le 10^5$

如果把往上45度想成左括號，往下45度想成右括號。
可以發現合法的山稜線肯定會是一組合法的括號匹配。
因此問題就是: 給定$n$，問有$\frac{n}{2}$組括號會有幾種括號匹配?

而$n$組括號的括號匹配正是卡特蘭數$C_n$，我們有
$$C_n=\frac{1}{n+1}{2N\choose N}$$
只要預處理階乘配合模逆元計算就好。
複雜度$\mathcal{O}(TlogMOD+N)$。(MOD=1e9+7)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
const int MOD     = 1e9+7;
/*--------------------------------------------------------------------------------------*/

const int N = 1e6 + 25;
ll frac[N];

ll mpow(ll a, int b) {
	ll res = 1;
	for(; b; b >>= 1, a = a * a % MOD)
		if(b & 1)
			res = res * a % MOD;
	return res;
}
ll c(int n, int m) {
	return frac[n] * mpow(frac[m], MOD - 2) % MOD * mpow(frac[n - m], MOD - 2) % MOD;
}

signed main() { EmiliaMyWife
	frac[0] = 1;
	for(int i = 1; i < N; i++)
		frac[i] = frac[i - 1] * i % MOD;

	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		cout << c(n, n / 2) * mpow(n / 2 + 1, MOD - 2) % MOD << '\n';
	}
}