24979. She was in Love with BST

Given a integer n, you have to tell the sum of number of structurally unique Binary search trees built on different permutations of the set{x , x belongs to [1..n] and x is an integer}.

A Binary Search tree is said to be built on a permutation iff the inorder traversal of that BST is same as the permutation.

A permutation is said to be distinct from another if there exists a position i such that the i th element of both the permutations is different.

The answer can be very large so output this number modulo 1908 .

Morover, you know that inorder traversal of a Binary search tree is unique.

Input. The first line consists of the number of test cases t (1 ≤ t ≤ 1000). The following t lines consists of a single integer n (1 ≤ n ≤ 1000).

Output. Print t lines each consisting of the answer to the problem modulo 1908.

Sample input	Sample output
2 1 2	1 2

РЕШЕНИЕ

комбинаторика – числа Каталана

Анализ алгоритма

Количество искомых бинарных деревьев с n вершинами равно числам Каталана Cat_n = .

Для решения задачи вычислим все значения биномиальных коэффициентов для k, n ≤ 2000 по модулю 1908.

Поскольку вычисления происходят по модулю, делить на (n + 1) нельзя – результат будет неверный. Для этого воспользуемся формулой:

= –

Доказательство.

– = = =

= = =

Реализация алгоритма

#include <stdio.h>

#include <string.h>

#define MAX 2030

#define MOD 1908

int cnk[MAX][MAX];

int n, tests;

void FillCnk(void)

{

int n, k;

memset(cnk,0,sizeof(cnk));

for(n = 0; n < MAX; n++) cnk[n][0] = 1;

for(n = 1; n < MAX; n++)

for(k = 1; k <= MAX; k++)

cnk[n][k] = (cnk[n-1][k] + cnk[n-1][k-1]) % MOD;

}

int main(void)

{

FillCnk();

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

printf("%d\n",(cnk[2*n][n] - cnk[2*n][n - 1] + MOD) % MOD);

}

return 0;

}