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;
}