問題一覧 > 通常問題

No.3169 [Cherry 7th Tune] Desire for Approval

レベル : / AI推定難易度 : 2700 / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 11
作問者 : 👑 Kazun / テスター : 👑 Nachia
お気に入りにしたユーザー ProblemId : 10163 / 自分の提出
問題文最終更新日: 2025-05-25 18:30:06
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 468 Desire for Approval ~Ash blown by the draft leads to the door to a new beginning~ (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。