codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2182D.md (2599B)


      1 Source: https://codeforces.com/problemset/problem/2182/D
      2 
      3 D. Christmas Tree Decoration
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 A group of $n$ people decided to decorate the Christmas tree. They have $(n+1)$ boxes of decorations, numbered from $0$ to $n$. Initially, the $i$-th box contains $a_i$ decorations.
     22 
     23 We say that a permutation $p$ of size $n$ (an array of size $n$ where each number from $1$ to $n$ appears exactly once) is fair if it is possible to hang all the decorations on the tree using the following process:
     24 
     25 * person $p_1$ takes a decoration either from box $0$ or from box $p_1$, and hangs it on the tree;
     26 * person $p_2$ takes a decoration either from box $0$ or from box $p_2$, and hangs it on the tree;
     27 * and so on;
     28 * after person $p_n$, person $p_1$ follows, and the process repeats until all the decoration are on the tree.
     29 
     30 During this process, there should never be a situation where person $i$ needs to hang a decoration, but both box $0$ and box $i$ are empty. If such a situation cannot be avoided, the permutation is not fair. However, if the people can choose from which box to take a decoration during each step in such a way that this situation does not arise, then the permutation is fair.
     31 
     32 Your task is to calculate the number of fair permutations. Since the answer may be large, output it modulo $998244353$.
     33 
     34 Input
     35 
     36 The first line contains a single integer $t$ ($1 \le t \le 5000$) — the number of test cases.
     37 
     38 The first line of each test case contains a single integer $n$ ($1 \le n \le 50$).
     39 
     40 The second line contains $(n+1)$ integers $a_0, a_1, \dots, a_n$ ($0 \le a_i \le 10^6$).
     41 
     42 Output
     43 
     44 For each test case, print a single integer — the number of fair permutations, taken modulo $998244353$.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 4
     52 
     53 3
     54 
     55 1 2 1 0
     56 
     57 3
     58 
     59 1 0 2 0
     60 
     61 1
     62 
     63 2 5
     64 
     65 4
     66 
     67 6 1 4 2 1
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 2
     74 
     75 0
     76 
     77 1
     78 
     79 12
     80 ```
     81 
     82 Note
     83 
     84 In the first example, the fair permutations are $[1, 2, 3]$ and $[1, 3, 2]$.
     85 
     86 Let's take a closer look at the Christmas tree decoration for permutation $[1, 3, 2]$:
     87 
     88 * the person $p_1=1$ hangs a decoration from the box $1$;
     89 * the person $p_2=3$ hangs a decoration from the box $0$;
     90 * the person $p_3=2$ hangs a decoration from the box $2$;
     91 * the person $p_1=1$ hangs a decoration from the box $1$.
     92 
     93 Note that if the person $p_1=1$ takes the decoration from the box $0$ during the first step, then the person $p_2=3$ won't be able to perform the next step (since both boxes $0$ and $3$ will be empty). However, since this situation can be avoided, the permutation is fair.