Editorial : H. Counting Sort?

For a length-$n$ array $b$ with entries in $\{0,\ldots,n\}$, define $f(b)$ by

Zeros in $b$ do not appear as $f(b)_0$; they only reduce how many positions can carry positive symbols.

Starting from $d=b$, iterate $d \gets f(d)$ and collect distinct arrays in a set. Let $g(b)$ be how many distinct arrays appear before any repeat. Equivalently, walk the functional graph $x \mapsto f(x)$ from $b$ until the first repeated vertex; then $g(b)$ is the number of distinct vertices on that initial segment.

We want counts of arrays $a$ with bounds $0 \le a_i \le r_i$ such that $g(a)=p$. This note concentrates on uniform bounds

so every index may take any value in $\{0,\ldots,n\}$. The full contest problem uses the same DP skeleton with position-dependent caps $R_x$.

Write $h_v$ for the number of indices $i$ with $a_i=v$, for $v=1,\ldots,n$. The vector $(h_1,\ldots,h_n)$ is the restriction of the usual histogram to positive labels; zeros are summarized by

Lemma. For each $t \ge 1$, the multiset of entries of $f^t(a)$ is determined by $f^{t-1}(a)$. Hence the whole trajectory $(f^t(a))_{t \ge 0}$ depends only on the multiset of entries of $a$, i.e.\ on $(h_0,h_1,\ldots,h_n)$. In particular, permuting positions of $a$ does not change $g(a)$.

So when we count arrays later, we may first group by a discrete summary of $a$, then refine only where that summary does not fix $g$.

Fix $r_i=n$ for all $i$. Build $(h_1,\ldots,h_n)$ by processing values from large to small:

1. Among the $n$ indices, choose how many equal $n$. Call this number $\mathrm{cnt}_n \in \{0,\ldots,n\}$.
2. Among the remaining $n-\mathrm{cnt}_n$ indices that still carry $0$, choose how many equal $n-1$. Call this $\mathrm{cnt}_{n-1}$, and so on.
3. After fixing $\mathrm{cnt}_n,\ldots,\mathrm{cnt}_1$, every index still at $0$ stays $0$.

Let $S_k = \mathrm{cnt}_n + \cdots + \mathrm{cnt}_{k+1}$ be how many indices already received a positive label strictly larger than $k$. When we are about to choose $\mathrm{cnt}_k$, exactly $n - S_k$ indices are still zero. All of them may become $k$, because every $r_i \ge k$. Therefore

Running product over $k=n,n-1,\ldots,1$ counts arrays $a$ that realize the chosen tuple $(\mathrm{cnt}_n,\ldots,\mathrm{cnt}_1)$.

Discard labels $k$ where $\mathrm{cnt}_k=0$. The nonzero tuple entries form a multiset of positive integers:

(a multiset: order of levels does not matter when we forget which value $k$ produced which count). Store $M(a)$ as a sorted list in non-increasing order; that sorted word is a canonical key.

Interpretation. Think of $(h_1,\ldots,h_n)$ as bar lengths. The positive $h_v$ form a composition of $\sum_v h_v$ into some parts; $M(a)$ forgets which value $v$ produced which bar height and keeps only the multiset of heights that occurred.

Incremental construction matches inserting one positive integer $\mathrm{cnt}_k$ into this multiset when we finish level $k$. Starting from empty and processing $k=n,\ldots,1$, after handling levels down to $k$ the multiset holds exactly the positive counts among $\mathrm{cnt}_n,\ldots,\mathrm{cnt}_k$. Let $\mathrm{sum}(M)$ denote the sum of elements of $M$. After levels $n,\ldots,k+1$ are processed,

So before choosing $\mathrm{cnt}_k$, the number of indices still free is $n - \mathrm{sum}(M)$, matching $\binom{n-\mathrm{sum}(M)}{\mathrm{cnt}_k}$.

Let $\mathrm{dp}[M]$ be the number of arrays $a \in \{0,\ldots,n\}^n$ whose multiset of positive histogram counts is exactly $M$. Initialize $\mathrm{dp}[\emptyset]=1$. For each $k=n,n-1,\ldots,1$, update

whenever $M'$ arises from $M$ by inserting one copy of $\mathrm{cnt}$ (and $\mathrm{cnt}=0$ leaves $M$ unchanged). Only finitely many keys $M$ appear because $\mathrm{sum}(M)\le n$ and each element is between $1$ and $n$.

This is exactly “distributing” counts level by level: factorials modulo $998\,244\,353$ give binomial coefficients.

For almost all arrays, $g(a)$ is determined already by $M(a)$. Two constructions line up:

Given a multiset $M$ of positive integers written in non-increasing order as a word $s$ (each letter is a part size), define $\mathrm{Nxt}(s)$:

1. Split $s$ into maximal runs of equal letters; let $a_1,a_2,\ldots$ be the run lengths.
2. Sort $(a_1,a_2,\ldots)$ in non-increasing order and concatenate as the next word.

So $\mathrm{Nxt}$ merges equal part sizes, reads how many copies of each size appeared, and writes those counts as the new multiset of parts. This is the same combinatorial move as passing from a histogram vector to the histogram of its positive entries, after sorting.

Define a depth $\mathrm{dep}(s)$ by

• $\mathrm{dep}(\text{empty}) = 1$;
• if $s$ is a single symbol with value $1$, then $\mathrm{dep}(s)=2$;
• otherwise $\mathrm{dep}(s)=1+\mathrm{dep}(\mathrm{Nxt}(s))$.

Match the orbit of $f$ on $a$ to iterations of $\mathrm{Nxt}$ on $M(a)$. Then:

• If $M(a)=\emptyset$, equivalently $a=\mathbf{0}$, then $f(a)=a$ and $g(a)=1$. Do not plug $M=\emptyset$ into $1+\mathrm{dep}$; that formula is for nonempty $M$.
• If $M(a)$ is nonempty and not the exceptional singleton $\{1\}$, then $g(a)=1+\mathrm{dep}(M(a))$.

The auxiliary values $\mathrm{dep}(\cdot)$ are arranged so that $1+\mathrm{dep}(M)$ agrees with $g(a)$ once $M=M(a)$ is nonempty and not the $\{1\}$ fibre; the all-zero case is always handled by $M=\emptyset$ and $g=1$.

Suppose $M(a)=\{1\}$: exactly one index carries a nonzero value in $\{1,\ldots,n\}$, and that value appears once. The abstract multiset does not record which index is nonzero nor which value $v \in \{1,\ldots,n\}$ was chosen. Those discrete choices change $g(a)$ (compare $[1,0]$ with $[2,0]$ for $n=2$ in the statement note).

Let $w=\mathrm{dp}[\{1\}]$. Under uniform caps one checks $w=n^2$: choose which of $n$ indices is nonzero ($n$ ways) and which value in $\{1,\ldots,n\}$ it takes ($n$ ways). Split $w$ by which index carries the nonzero and which value $v \in \{1,\ldots,n\}$ it carries:

• One distinguished pattern (depending on how you index the input) contributes to $g=1$.
• Exactly $n-1$ patterns with value $1$ off that distinguished coordinate contribute to $g=2$.
• All $w-n$ remaining one-nonzero arrays contribute to $g=3$.

With general bounds $r_i$, the same split uses $R_1=|\{i:r_i\ge 1\}|$ and whether the first coordinate may display a $1$.

Algorithm:

1. Precompute factorials and inverse factorials modulo $998\,244\,353$ up to $n$.

2. Run the layered DP over $k=n,\ldots,1$, maintaining $\mathrm{dp}[M]$ as above.

3. After the last layer, for each multiset $M$ with weight $w=\mathrm{dp}[M]$:

   • If $M=\emptyset$, add $w$ to the count for $g=1$ (all-zero arrays).
   • If $M=\{1\}$, split $w$ according to how many single-nonzero arrays fall into the three behaviours above (under uniform caps, rank-and-file counting).
   • Else add $w$ to the count for $p = 1+\mathrm{dep}(M)$ when $p \le k$.

Here $\mathrm{sum}(M)\le n$ and each multiset element lies in $\{1,\ldots,n\}$. Distinct keys inject into multisets built from counts at each layer, so their count grows like integer partition counts—subexponential in $n$, still tiny for $n \le 50$. Each layer tries $O(n)$ values of $\mathrm{cnt}$ per state.

Replace the factor $n-\mathrm{sum}(M)$ by $R_k-\mathrm{sum}(M)$, where

Only indices that may still equal $k$ participate in $\binom{R_k-\mathrm{sum}(M)}{\mathrm{cnt}}$. The multiset update is unchanged; the bookkeeping for the $\{1\}$ fibre uses the same geometric idea but with asymmetric $r_i$.

For $r_i=n$, count arrays by sweeping values downward, tracking only the multiset $M(a)$ of positive histogram counts. Binomial coefficients count assignments of indices at each level. Almost every fibre is classified by iterating $\mathrm{Nxt}$ on $M(a)$ and reading off $1+\mathrm{dep}(M)$; the all-zero array and the singleton-multiset refinement handle the remaining small-$g$ behaviour.