Description

We define a tree valid if and only if on each node there is a number in $S$, and the value of this true is define as the sum of these numbers.

Given $n,m,S$, for each $k$ in $[1,m]$ find out the number of valid binary trees with $n$ nodes and value $k$.

Tutorial

Define the OGF to the answer as $F$, and $G(x) = \sum_{k=0}^\infty [k \in S]x^k$.

We know that a binary tree is defined as follow:

• An empty tree is a binary tree
• The combination of a root and two son binary trees(with order)

The there is clear that

So

As is obviously that

We know the $\pm$ should be $+$

Code

ref: local , complete

#include "~/code/Math/Poly/main.h"
void solve()
{
 using namespace Polys;
 int n = sc.n(), m = sc.n();
 Poly A(m+1);
 rep (i,n) { 
   int u = sc.n();
   if (u <= m) A[u] -= 4; }
 A[0] = 1;
 A = A.sqrt();
 A[0] = 2;
 A = A.inv();
 A *= Int(2);
 repa (i,m) printf("%u\n", static_cast<unsigned>(A[i]));
}