PROBLEM LINK:Author: Satyaki Upadhyay PROBLEMCount number of semiBSTs having exactly $n$ nodes. A semiBST is a tree with $n$ nodes which satisfies the following conditions:
Constraints: $n \le 10^5,$ $\text{test cases} \le 10^5.$ Print the answer modulo $663224321$ i.e. $2^{19} \times 5 \times 11 \times 23 + 1$. PREREQUISITESKnowledge of "online" FFT trick. EXPLANATIONWe first solve the problem in $O(n^2)$, and then optimize it using a trick. An $O(n^2)$ SolutionWe use a dynamic program similar to "count number of BSTs having $n$ nodes". Define $T(n)$ to be number of semiBSTs of size $n$. To find a recurrence for $T(n)$, we will iterate over the number of nodes in the left subtree. Note that fixing the number of nodes in the left subtree determines the value of the root. Suppose we say that the left subtree has $i$ nodes. Then, the number of labeled trees with $i$ nodes is $i^{i  2}$ by Cayley's Formula. Thus, the number of ways for us to choose a left subtree is $i \times i^{i  2} = i^{i  1}$ since we have $i$ choices for the root of the left subtree as well. By definition, the right subtree can be chosen in $T(n  1  i)$ ways. Note that these two are independent, making our recurrence: $T(n) = \sum_{i = 0}^{n  1} (i^{i  1} \times T(n  1  i))$ with base cases $T(0) = T(1) = 1$. Clearly, there are $O(n)$ states, and it takes $O(n)$ to compute each state. Therefore, this solution is $O(n^2)$. Speedup using Online FFTIt turns out that we can speed up the above dynamic program using a trick known as online FFT. The special modulo would have given this hint as well! For reference, please solve this Codeforces problem. The editorial for this problem explains this trick! Additionally, you can check out these brilliant slides written by Tanuj Khattar! Interestingly, his team TooWeakTooSlow were the only team to solve this problem in the onsite regional. The final complexity would be $O(n \log^2{n})$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 28 Dec '17, 14:43

Alternate (much simpler?) solution using generating functions: https://www.codechef.com/viewsolution/18002620 Let s[i] = i * (i 1), and t[n] be the answer for n nodes. S(z) = s[0] * x^0 + s[1] * x^1 + ..... T(z) = t[0] * x^0 + t[1] * x^1 + ..... T(z) = z * S(z) * T(z) + 1 T(z) = 1 / (1  z * S(z)) Use polynomial inverse to get AC. (Refer http://codeforces.com/problemset/problem/438/E for more details) answered 01 Apr '18, 09:47
