HackerRank Number Theory – Lucy and Flowers

Challenge: Lucy and Flowers

Subdomeniu: Number Theory (number-theory)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464734927

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/lucy-and-flowers/problem

Cerinta

Little Lucy loves to arrange her flowers in patterns similar to those of a binary search tree. Her father, a computer scientist himself, takes note of this and finds out that she has *N* flowers. Every day she takes some of these *N* flowers and arranges them into all possible different patterns. The more the number of arrangements, the more time she spends outside.

Now, her father knows that she takes a non-empty subset of these *N* flowers any given day. He wants to 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 10<sup>9</sup>+9 if the answer is no less than 10<sup>9</sup>+9. 
  
**Note:** All flowers are distinct and are labelled by distinct numbers.


**Input Format**  
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 Format**  
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    

**Explanation**

For the first case, only one BST is possible.  
For the second case, only 4 BSTs are possible (shown below). 

    1    2    1      2
               \    / 
                2   1

Similarly, 14 BSTs are possible for *N* = 3, and 50 are possible for *N* = 4.

Cod sursa

//lucy-and-flowers.cpp
//Lucy and Flowers
//Weekly Challenges - Week 4
//Author: derekhh

#include<cstdio>
#include<cstring>
using namespace std;

const int MOD = 1000000009;

long long f[5001];
long long c[5001][5001];
long long memo[5001];

void init()
{
	f[0] = f[1] = 1;
	for (int i = 2; i <= 5000; i++)
	{
		for (int j = 1; j <= i; j++)
			f[i] = (f[i] + (f[j - 1] * f[i - j]) % MOD) % MOD;
	}
}

void initc()
{
	for (int i = 1; i <= 5000; i++)
		c[i][0] = c[i][i] = 1;
	for (int i = 2; i <= 5000; i++)
		for (int j = 1; j <= i; j++)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
}

int main()
{
	init();
	initc();
	memset(memo, -1, sizeof(memo));
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n;
		scanf("%d", &n);
		if (memo[n] != -1)
			printf("%lld\n", memo[n]);
		else
		{
			long long ret = 0;
			for (int i = 1; i <= n; i++)
				ret = (ret + c[n][i] * f[i]) % MOD;
			printf("%lld\n", ret);
			memo[n] = ret;
		}
	}
	return 0;
}