UVa 12887 - The Soldier's Dilemma

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

N 個人不同高，現在佔一排，任挑三個人的身高從左向右的相對高度，不存在矮、高、中的情況有多少種。

Sample Input

2
2
3

Sample Output

2
5

Solution

卡塔蘭數 (Catalan number)。

每一次考慮加入一個最高的人，窮舉最高的人應該佔在哪個位置，則其左、右側也要滿足定義，同時左側的人都要比右側的人高。最後得到公式如下，與卡塔蘭數相同。

#include <stdio.h> 
/*
add tallest people in position i
ways[n] = \sum ways[i] * ways[n-i-1].
			   ^^^^^^[1] ^^^^^^^^^^[2]
[1] left tree pos[0, i-1]
[2] right tree pos[i+1, n-1]
then label of right tree must small than label of left tree
=> Catalan number, an = (4n-2)/(n+1) * an-1
*/
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
	long long la = 1, lb = 0, ra = 0, rb = 1;
	long long i = 0, t, mod = m;
	while(n%m) {
		if(!i) {
			la -= n/m*ra, lb -= n/m*rb;
		} else {
			ra -= n/m*la, rb -= n/m*lb;
		}
		i = !i;
		t = n, n = m, m = t%m;
	}
	return i ? (la%mod+mod)%mod : (ra%mod+mod)%mod;
}
#define MAXN 5005
long long Catalan[MAXN];
const long long mod = 1000000007LL;
int main() {
	Catalan[0] = Catalan[1] = 1;
	for (int i = 2; i < MAXN; i++) {
		Catalan[i] = Catalan[i-1] * (4 * i - 2) %mod;
		Catalan[i] = Catalan[i] * inv(i+1, mod) %mod;
	}
	int n, testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		printf("%lld\n", Catalan[n]);
	}
	return 0;
}