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

1
2
3
2
2
3

Sample Output

1
2
2
5

Solution

卡塔蘭數 (Catalan number)。

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

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