Problem
Little Lucy loves to arrange her flowers in patterns similar to those of a binary search tree. Every day she takes some of the N flowers and arranges them into all possible different patterns. Find out the total number of arrangements that she can ever make. As this may be too large to handle, you only need to report final answer modulo 109+9 if the answer is no less than 109+9.
Input
The first line contains an integer T, the number of test cases.
The next T lines contain an integer each N, that denotes the number of flowers the girl has.
Output
Output T lines each containing an answer to corresponding query.
Constraints
- 1 <= T <= 5000
- 1 <= n <= 5000
Sample Input
4 1 2 3 4
Sample Output
1 4 14 50
Solution
Approach
We know that, the number of possible Binary Search Trees with n keys is Catalan Number (Cn). Now total number of arrangements that could be made with a subset of size r from a set of n numbers is (nCr*Cr)%mod (Cr: rth Catalan number). You could learn about finding Catalan Number (Cn) and Binomial Coefficient (nCr) from the following posts:
Code Implementation
//
// main.cpp
// Lucy and Flowers
//
// Created by Himanshu on 03/04/22.
//
#include <iostream>
#define MAX_SIZE 5000
#define mod 1000000009
using namespace std;
typedef long long ll;
ll C[MAX_SIZE+1][MAX_SIZE+1];
ll CN[MAX_SIZE+1];
ll ans[MAX_SIZE+1];
// Calculate Binomial Coefficient C(n, r)
void calculateBinomialCoeff () {
for (int i=0; i<=MAX_SIZE; i++) {
for (int j=0; j<=i; j++) {
// first and last binomial coefficients are
// always 1
if (j == 0 || j == i) {
C[i][j] = 1;
} else {
C[i][j] = (C[i-1][j-1] + C[i-1][j])%mod;
}
}
}
}
// Calculate Cn
void calculateCatalanNum () {
// Base Cases
CN[0] = CN[1] = 1;
for (int i=2; i<=MAX_SIZE; i++) {
for (int j=0; j<i; j++) {
CN[i] = (CN[i]%mod + (CN[j] * CN[i - j - 1])%mod)%mod;
}
}
}
void solve () {
for(int i=1; i<=MAX_SIZE; i++) {
ll temp = 0;
for (int j=1; j<=i; j++) {
temp = (temp%mod + (C[i][j]*CN[j])%mod)%mod;
}
ans[i] = temp;
}
}
int main () {
ll T, n;
calculateBinomialCoeff();
calculateCatalanNum();
solve();
cin>>T;
while (T--) {
cin>>n;
cout<<ans[n]<<endl;
}
return 0;
}
Time complexity: O(n2)