牛客网 E.弦 初见卡特兰数

题目地址

组合数学

答案是 2^n / (n + 1)!。概率可以通过合法方案数/总方案数来计算。合法方案数 f(n)=Σf(i) * f(n-i-1), 即为卡特兰数，故 f(n)=C(2n, n) / (n + 1)。总方案数为 C(2n, 2) * C(2n – 2, 2) … C(2, 2) / n! = (2n)! / n! / 2^n。两者相除即为答案。除法取模的话用逆元来计算（即费马小定理）。 总复杂度O(n)。

卡特兰数讲解

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define pb push_back
#define pf push_front
#define INF 0x3f3f3f3f
#define MAXN (int) 2e6 + 7
#define all(a) a.begin(), a.end()

typedef long long ll;

const ll mod = 1e9 + 7;
const double PI = acos(-1);

using namespace std;

int N, M, K, T;

long long fpow(long long a, long long b)
{
	if (a == 0)
		return 0;

	long long ans = 1;
	for (; b; b >>= 1, a = (a % mod * a% mod) % mod)
		if (b & 1) ans = (ans % mod * a % mod) % mod;
	return ans;
}


//quick_pow(a, p - 2); 逆元 mod;
signed main(void) {

#ifdef Sunshine
	freopen("data.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll n;
	cin >> n;

	ll ans = 1;
	for (int i = 2; i <= n + 1; i++) {
		ans = (ans * i) % mod;
	}

	cout << fpow(2, n) * fpow(ans, mod - 2) % mod << '\n';










#ifdef Sunshine
	freopen("CON", "r", stdin);
	system("pause");
#endif
	return 0;
}