Editorial : Christmas Tree Decoration
Suppose the permutation is fixed: $p_1, p_2, \dots, p_n$.
Let
$$ S = \sum_{i=0}^{n} a_i, \qquad k = \left\lfloor \frac{S}{n} \right\rfloor, \qquad r = S \bmod n. $$Interpretation:
- during the first $k$ full rounds, every person appears exactly $k$ times;
- then only $p_1, p_2, \dots, p_r$ appear one more time.
Person $i$ needs $k$ decorations from boxes $i$ and $0$. If $a_i < k$, the missing amount must come from box $0$:
$$ d_i = \max(0,\; k - a_i). $$Necessary condition:
$$ \sum_{i=1}^{n} d_i \le a_0. $$If this fails, the permutation is impossible immediately.
Assume it holds, and pay all these deficits from box $0$. Define leftovers:
$$ b_i = \max(0,\; a_i - k), \qquad b_0 = a_0 - \sum_{i=1}^{n} d_i. $$Only the first $r$ people in permutation order get one extra turn. So each personal box $i$ can be used at most once after the first $k$ rounds:
$$ b_i \le 1 \quad \forall i \in [1,n]. $$If some $b_i > 1$, impossible.
Now assume all $b_i \in \{0,1\}$. If $b_i = 1$ but $i$ is not in $\{p_1,\dots,p_r\}$, that decoration in box $i$ can never be taken. So for a fixed permutation, we need:
all indices with $b_i = 1$ are inside the first $r$ positions.
Together with $\sum d_i \le a_0$ and $b_i \le 1$, this is also sufficient.
Now permutation is not fixed. After the same preprocessing, define:
- $z =$ number of indices $i \in [1,n]$ with $b_i = 0$;
- $o = n - z =$ number of indices with $b_i = 1$.
Also:
$$ r = S \bmod n = b_0 + \sum_{i=1}^{n} b_i = b_0 + o. $$So the first $r$ positions must contain:
- all $o$ one-indices (mandatory),
- plus exactly $b_0$ zero-indices.
If $b_0 > z$, impossible.
Otherwise:
- Choose which zero-indices go to the first $r$: $\binom{z}{b_0}$.
- Permute the first $r$ positions: $r!$.
- Permute the remaining $n-r = z-b_0$ positions: $(z-b_0)!$.
Hence
\frac{z! \cdot (n-z+b_0)!}{b_0!}. $$
This is exactly what the model solution computes.
After paying deficits for the mandatory $k$ rounds, every fair process has exactly
$$ b_0 + \sum_{i=1}^{n} b_i = r $$decorations left, and exactly $r$ future turns remain (the first $r$ positions in the next round).
- Any $b_i > 1$ is impossible because person $i$ gets at most one of those turns.
- Any $b_i = 1$ outside the first $r$ positions is impossible because that turn never occurs.
- If all one-indices are inside first $r$, all remaining required extra decorations come from box $0$, and their count is exactly $b_0$.
So the characterization and counting above are complete.
- Precompute factorials up to $50$.
- Use fast exponentiation for modular inverse: $x^{-1} \equiv x^{MOD-2} \pmod{MOD}$.
- Per test:
- compute $S, k$;
- iterate $i=1..n$, update deficits and leftovers, detect bad cases;
- if valid, apply the formula.
- Time: $O(n)$ per test case.
- Memory: $O(1)$ besides factorial table.