Solution to Gym-103081 Mentors (SWERC 2020 Problem F)

A combinatorics problem on tree.

Problem description:

Counting without restriction on leaves

First consider $g(n)$, defined as the number of ways the tree can be formed using $n$ nodes (without restrictions on leaves).

Node $n$ must be the root of the tree. Then we can choose $k$ nodes in the left child and $(n-1-k)$ nodes in the right child, and form the sub-trees separately. However, when $k=n-1-k$, the number of possible ways should be halved, as the left and right children should be seen as the same.

Therefore, when $n$ is even,

$$
g(n)=\sum_{k=0}^{\lfloor(n-1)/2\rfloor}\binom{n-1}{k}g(k)g(n-1-k).
$$

When $n$ is odd,
$$
g(n)=\left( \sum_{k=0}^{(n-1)/2 - 1}\binom{n-1}{k}g(k)g(n-1-k) \right)+ \frac12 \binom{n-1}{\frac{n-1}2}g^2\left(\frac{n-1}2\right).
$$
Edge cases: $g(0) = g(1) = 1$.

Counting with restriction on leaves

Denote $f(n, r)$ as the number of ways the tree can be formed with $n$ nodes and with node $r$ being a leaf.

Consider subtracting all the illegal cases from $g(n)$. By illegal, we mean the size of node $r$’s subtree is larger than $1$. When its size is $m$ $(2 \le m \le r)$, we

select which $m$ nodes are included in the subtree, with $\binom{r-1}{m-1}$ ways,
form a subtree using $m$ nodes, with $g(m)$ ways, and
seeing the subtree together as a single node, form a tree with $(n-m+1)$ nodes and with node $(r-m+1)$ (the entire subtree) being a leaf, which has $f(n-m+1, r-m+1)$ ways.

Thus we have
$$
f(n, r) = g(n) - \sum_{m=2}^{r}\binom{r-1}{m-1} g(m) f(n-m+1, r-m+1).
$$

Also notice that $f(n, 1)=g(n)$, since node $1$ should always be a leaf.

Implementation

We need the answer modulo $M$. Use the equation
$$
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
$$
and produce a table for the binomial numbers in $O(n^2)$ time.

We have an annoying $\frac 12$ in the calculation of $g(n)$. There is no guarantee of multiplicative inverse as $M$ might not be prime. The trick is to notice

$$
\frac12 \binom{2n}{n} = \binom{2n-1}{n-1} = \binom{2n-1}{n}.
$$

#include<bits/stdc++.h>
using namespace std;
#define rep(i,from,to) for(int i=(int)(from);i<=(int)(to);++i)
#define rev(i,from,to) for(int i=(int)(from);i>=(int)(to);--i)
#define For(i,to) for(int i=0;i<(int)(to);++i)
#define mmst(a,x) memset(a, x, sizeof(a))
typedef long long ll;
ll M;
const ll N = 2444;
ll C[N][N];
ll g[N];
ll mem[N][N];
ll solve(ll n, ll r) {
    if (mem[n][r] != -1) return mem[n][r];
    if (n == 0) return 1;
    if (r == 1) return g[n];
    ll ans = g[n];
    rep(k,2,r) {
        ans -= (((C[r-1][k-1] * g[k]) % M) * solve(n - k + 1, r - k + 1)) % M;
        ans %= M;
    }
    ans = (ans + M) % M;
    return mem[n][r] = ans;
}

int main() {
    ll n, r;
    cin >> r >> n >>  M;
    if (M == 1) {
        cout << 0 << endl;
        return 0;
    }
    rep(i,0,n) C[i][0] = C[i][i] = 1;
    rep(i,2,n) {
        rep(j,1,i-1) {
            C[i][j] = C[i-1][j] + C[i-1][j-1];
            C[i][j] %= M;
        }
    }
    g[0] = 1;
    g[1] = 1;
    g[2] = 1;
    rep(i,3,n) {
        rep(j,0,i-1) {
            int k = (i-1) - j;
            if (j > k) break;
            if (j != k) {
                g[i] += (((g[j] * g[k]) % M) * C[i-1][j]) % M;
                g[i] %= M;
            }
            else {
                g[i] += (((g[j] * g[j]) % M) * C[i-2][j-1]) % M;
                g[i] %= M;
            }
        }
    }
    mmst(mem, -1);
    cout << solve(n, r) << endl;
    return 0;
}