Nezzar and Chocolate Bars
Contest: Codeforces Round 698 (Div. 1)
Difficulty rating: 3500
Tags: combinatorics, fft, math, probabilities

Nezzar buys his favorite snack — $$$n$$$ chocolate bars with lengths $$$l_1,l_2,\ldots,l_n$$$. However, chocolate bars might be too long to store them properly!

In order to solve this problem, Nezzar designs an interesting process to divide them into small pieces. Firstly, Nezzar puts all his chocolate bars into a black box. Then, he will perform the following operation repeatedly until the maximum length over all chocolate bars does not exceed $$$k$$$.

- Nezzar picks a chocolate bar from the box with probability proportional to its length $$$x$$$.
- After step $$$1$$$, Nezzar uniformly picks a real number $$$r \in (0,x)$$$ and divides the chosen chocolate bar into two chocolate bars with lengths $$$r$$$ and $$$x-r$$$.
- Lastly, he puts those two new chocolate bars into the black box.

Nezzar now wonders, what is the expected number of operations he will perform to divide his chocolate bars into small pieces.

It can be shown that the answer can be represented as $$$\frac{P}{Q}$$$, where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q \not \equiv 0$$$ ($$$\bmod 998\,244\,353$$$). Print the value of $$$P\cdot Q^{-1} \mod 998\,244\,353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 50, 1 \le k \le 2000$$$).

The second line contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \le l_i$$$, $$$\sum_{i=1}^{n} l_i \le 2000$$$).

Output format:
Print a single integer — the expected number of operations Nezzar will perform to divide his chocolate bars into small pieces modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Example input:
1 1
2

Example output:
4

Example input:
1 1
1

Example output:
0

Editorial:
Let's firstly solve an easier version where $$$n=1$$$.
Part 1 ($$$n = 1$$$)
Let's firstly rephrase the original task and solve it for case $$$n=1$$$.
- Let $$$p_k$$$ the probability of event that $$$X_{(i)}-X_{(i-1)} \le K$$$ for $$$1 \le i \le k$$$ and $$$L - X_{(k)} \le K$$$. Here, $$$k$$$ real numbers $$$X_1,X_2,\ldots,X_k$$$ are chosen uniformly from $$$(0,L)$$$, and $$$X_{(1)},X_{(2)},\ldots,X_{(k)}$$$ is the sorted array of $$$X_0=0,X_1,X_2,\ldots,X_k$$$. Then the disire answer would be $$$\sum_{k=0}^{+\infty} (1-p_k)$$$.
To simplify notations, denote $$$w=\frac{K}{L}$$$. We are aiming to calculate $$$p_n$$$ from now on.
Let $$$Z_i=X_{(i)}-X_{(i-1)}$$$，then the pdf(probability density function) of the union distribution of $$$Z_1,Z_2,\ldots,Z_n$$$ is
$$$$$$f(z_1,z_2,\ldots,z_n)=n! I_{0<z_i<1,\sum_{i=1}^n z_i < 1}$$$$$$
Hence,
$$$$$$p_n= n! \int_{0<z_i<w, 1-w < \sum_{i=1}^n z_i < 1} 1 dz_1 dz_2 \ldots dz_n= n! w^n \int_{0<z_i<1, \frac{1}{w}-1<\sum_{i=1}^n z_i<\frac{1}{w}} 1 dz$$$$$$
Consider $$$Y_1,Y_2,\ldots,Y_n$$$ i.i.d, where $$$Y_i$$$ follows uniform distribution sampling from $$$(0,1)$$$，then the integral above is $$$Pr[\frac{1}{w}-1<\sum_{i=1}^n Y_i<\frac{1}{w}]$$$。
Note that $$$\sum_{i=1}^n Y_i$$$ follows Irwin–Hall distribution whose CDF(cumulative distribution function) is $$$$$$F(x)={\frac {1}{n!}}\sum _{{k=0}}^{{\lfloor x\rfloor }}(-1)^{k}{\binom {n}{k}}(x-k)^{n}$$$$$$
Thus，$$$p_n = n!w^n(F(\frac{1}{w})-F(\frac{1}{w}-1))$$$。
$$$$$$p_n=1- \left(\sum_{k=0}^x (-1)^k \binom{n}{k} (1-wk)^n - \sum_{k=0}^{x-1} (-1)^k \binom{n}{k}(1-(k+1)w)^n\right) \\ =\sum_{k=1}^x (-1)^{k-1} \left(\binom{n}{k}+\binom{n}{k-1}\right)(1-kw)^n$$$$$$
where$$$x=\left[\frac{1}{w}\right]$$$。
using identity $$$\sum_{n \ge k}\binom{n}{k} x^n=x^k(1-x)^{-(k+1)}$$$ to finish this task.
Main version
To avoid confusion, we will let $$$q_{m,j}$$$ the probability that $$$m$$$ operations are performed on line $$$j$$$ but there still exists lines produced by line $$$j$$$ with length greater or equal to $$$K$$$ (which have been calculated in part 1, with notation $$$p_n$$$).
Recall that $$$q_{m,j} = \sum_{k=1}^{\lfloor \frac{L_j}{K} \rfloor} (-1)^{k-1}\binom{m+1}{k} (1-\frac{kK}{L_j})^m$$$.
Therefore, probability $$$p_m$$$ that one fails to finish the task within $$$m$$$ rounds is $$$$$$1 - \sum_{j_1+j_2+\ldots+j_n=m} \frac{m!}{j_1!j_2!\ldots j_n!} \prod_{r=1}^n (1-q_{j_r,r})\left(\frac{L_j}{L}\right)^{j_r} $$$$$$
Let $$$Q_j$$$ be EGF of sequence $$$((1-q_{m,r} )L_j/L)_{m \ge 0}$$$, that is to say the $$$m$$$-th coefficient is $$$$$$[x^m]Q_j = \frac{1}{m! L}(1-q_{m,r} )L_j.$$$$$$
Similarly, let $$$P$$$ be EGF of sequence $$$(p_m)_{m \ge 0}$$$, one may observe that $$$$$$P = \exp(x) - \prod_{i=1}^n Q_i.$$$$$$
In the following part, we will calculate $$$Q_j$$$.
$$$$$$ \begin{aligned} Q_j &= \sum_{m \ge 0} \frac{1}{m!} \left(\frac{L_j}{L} - \sum_{k=1}^{\lfloor \frac{L_j}{K} \rfloor} (-1)^{k-1} \binom{m+1}{k} \left(1-\frac{kK}{L_j}\right)^m \right) x^m\\ &= \exp\left(\frac{L_j}{L}x\right) - \sum_{k=1}^{\lfloor \frac{L_j}{K} \rfloor} (-1)^{k-1} \sum_{m \ge k-1} \frac{(m+1)}{k!(m+1-k)!} \left(\frac{L_j-kK}{L}\right)^m x^m \end{aligned} $$$$$$
Note that $$$\sum_{m \ge k-1} \frac{m+1}{k!(m+1-k)!} y^m = \sum_{m \ge k} \frac{y^m}{k!(m-k)!} + \sum_{m \ge k-1} \frac{k y^m}{k!(m+1-k)!} = \frac{y^k}{k!} \exp(y) + \frac{y^{k-1}}{(k-1)!} \exp(y)$$$. Therefore,
$$$$$$ \begin{aligned} Q_j &= \exp(\frac{L_j}{L} x) - \sum_{k=1}^{\lfloor \frac{L_j}{K} \rfloor} (-1)^{k-1} \left(\frac{1}{k!} \left(\frac{L_j-kK}{L}\right)^k x^k + \frac{1}{(k-1)!} \left(\frac{L_j-kK}{L}\right)^{k-1} x^{k-1} \right)\exp\left(\frac{(L_j-kK)x}{L}\right) \end{aligned} $$$$$$
Note that with NTT and above equalities, we may calculate coefficient of $$$P$$$ in $$$O(nL \log nL)$$$ (Precisely, we will calculate coefficient of $$$x^{k-j}\exp{\left(1-\frac{K}{L}k x\right)}$$$ for each $$$0 \le k\le L$$$ and $$$0 \le j \le \min(n,k)$$$).
Lastly, we should notice that if EGF of sequence $$$a$$$ is $$$x^k \exp(Cx)$$$, then $$$a_{k+n} = \frac{(k+n)!}{n!}C^n$$$, and its OGF is $$$k!\sum_{n \ge 0}\binom{n+k}{k}C^n x^{n+k} = k!\frac{(x/C)^k}{(1-Cx)^{k+1}}$$$. Hence, we will be able to calculate OGF $$$P'$$$ of sequence $$$p_m$$$, and answer is exactly $$$P'(1)$$$.
It should be noticed that our approach will run in $$$O(nL \log nL)$$$ implemented appropriately , where $$$L=\sum_{i=1}^n l_i$$$. However, larger time limit is set to allow suboptimal solution to pass(like $$$O(nL^2)$$$ or $$$O(n^2L \log L)$$$).