2182D: Christmas Tree Decoration

Let

$S=a_0+a_1+\cdots+a_n.$

For a fixed permutation $p$ , the process lasts exactly $S$ turns, because every turn hangs exactly one decoration. After turn $S$ , everything is gone, so we stop. No one has to take a ghost decoration afterward. That final-stop detail matters.

Count turns, not choices

Suppose person $i$ appears $c_i$ times among the first $S$ turns.

Person $i$ is the only person who can take from box $i$ , so all $a_i$ decorations from box $i$ must be taken during those $c_i$ turns. Therefore we need

$a_i \le c_i.$

Is that also sufficient? Yep.

If $a_i\le c_i$ for every $i$ , then on exactly $a_i$ of person $i$ 's turns, take from box $i$ . On all remaining turns, take from box $0$ . The number of remaining turns is

= \sum_{i=1}^n c_i - \sum_{i=1}^n a_i = S - \sum_{i=1}^n a_i = a_0.$$ So the common box is used exactly $a_0$ times. Perfect. No extra hidden scheduling monster under the bed. Thus a permutation is fair iff $$a_i\le c_i \quad \text{for all } i.$$ **What are the $c_i$ values?** Write $$S=qn+r,\quad 0\le r<n.$$ During $S$ turns, every position in the permutation appears $q$ times. The first $r$ positions appear one extra time. So if person $i$ is in the first $r$ positions, then $$c_i=q+1,$$ otherwise $$c_i=q.$$ That means: - if $a_i>q+1$, impossible for every permutation; - if $a_i=q+1$, person $i$ **must** be placed in the first $r$ positions; - if $a_i\le q$, person $i$ can go anywhere. Tiny edge case: if $r=0$, there is no prefix with extra turns, so nobody can have $a_i=q+1$. The same rule handles it because then we need $m\le 0$. **Counting permutations** Let $$m = \#\{i\in[1,n] : a_i=q+1\}.$$ These $m$ forced people must all be inside the first $r$ positions. If $m>r$, answer is $0$. Otherwise: 1. choose and order the $m$ forced people inside the first $r$ positions; 2. fill every remaining position with the other $n-m$ people in any order. The count is $$\binom{r}{m}m!(n-m)!.$$ This simplifies to $$\frac{r!}{(r-m)!}(n-m)!.$$ Since $n\le 50$, we can precompute factorials and inverse factorials modulo $998244353$, or just compute the expression directly with factorials and modular inverses. Clean and boring, which is exactly what you want at 2 seconds. **Algorithm** For each test case: 1. compute $S$; 2. compute $q=\lfloor S/n\rfloor$ and $r=S\bmod n$; 3. scan $a_1,\dots,a_n$: - if any $a_i>q+1$, answer is $0$; - count how many equal $q+1$; 4. if that count is greater than $r$, answer is $0$; 5. otherwise output $$\binom{r}{m}m!(n-m)! \pmod{998244353}.$$ Complexity: $O(n)$ per test case after factorial precomputation. Memory: $O(n)$, basically nothing.

Christmas Tree Decoration

Progressive nudges

Full explanation

Generated C++