No.3169 [Cherry 7th Tune] Desire for Approval
Problem Visual
▶ Open to reveal the problem visual
Introduction
Slaves to social media, drenched in the desire for approval, are being born, $1$ person and then another $1$ person...
Problem Statement
On a social media platform called Sakurax, each $1$ message has $N$ metrics. Each metric takes a real value of $0$ or more.
Cherry-chan, a user of Sakurax, satisfies her desire for approval by posting messages on Sakurax.
For the metrics of a message, the $i$-th metric follows an Erlang distribution with shape parameter $k_i$ and scale parameter $a_i$.
That is, the $i$-th metric has as its probability density function the function $f_i(x)$ defined on the real numbers as follows. $$f_i(x)=\begin{cases} \dfrac{1}{(k_i-1)! a_i^{k_i} } x^{k_i-1} e^{-x/a_i} & (x \geq 0) \\ 0 & (x < 0)\end{cases}$$
The $N$ metrics are mutually independent.
For each of $m = 1, 2, \dots, N$, answer the following question.
The amount of desire for approval that Cherry-chan satisfies by posting a message is equal to the value that is the $m$-th smallest among the $N$ metrics ($m$-th in ascending order).
Let $E_m$ be the expected value of the amount of desire for approval that Cherry-chan satisfies by posting a message. Find $E_m \pmod{998244353}$.
Notes
Under the constraints of this problem, it can be proved that for each of $m=1,2, \dots, N$, there exists a pair of integers $(X,Y)$ satisfying the following.
- $Y$ is not a multiple of $998244353$.
- $Y \times E_m = X$.
For a pair of integers $X,Y$ satisfying these conditions, there exists a unique integer $Z$ between $0$ and less than $998244353$ such that $$Y \times Z \equiv X \pmod{998244353}$$ and using this integer $Z$, we define $E_m \pmod{998244353}:=Z$.
Although there are many possible pairs of integers $(X,Y)$ satisfying the conditions, $Z$ does not depend on the choice of $X,Y$ and is determined solely by $E_m$.
Constraints
- $1 \leq N \leq 12$.
- $1 \leq k_i \quad (1 \leq i \leq N)$.
- $k_1+\dots+k_N \leq 4000$.
- $1 \leq a_i \leq 20 \quad (1 \leq i \leq N)$.
- All inputs are integers.
Input
$N$ $k_1$ $a_1$ $k_2$ $a_2$ $\vdots$ $k_N$ $a_N$
Output
Output $E_m \pmod{998244353}$ in the order $m=1,2, \dots, N$, separated by spaces, on $1$ line.
Do not forget the newline at the end.
Sample
Sample 1
Input
2 1 2 2 3
Output
439227517 559016844
The $1$-st metric follows an Erlang distribution with shape parameter $1$ and scale parameter $2$.
Here, it can be proved that $E_1 = \dfrac{42}{25}, E_2 = \dfrac{158}{25}$. Then, since $$25 \times E_1 = 42, \quad 25 \times 439227517 \equiv 42 \pmod{998244353}$$ holds, we have $E_1 \pmod{998244353} = 439227517$.
Sample 2
Input
1 4 6
Output
24
When $N=1$, it can be proved that $E_1 = k_1 a_1$.
Sample 3
Input
10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Output
231989476 767777666 541286442 413771015 956738398 132234121 836358717 542139458 434737454 134190448
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun
Nachia