問題一覧 > 通常問題

No.3153 probability max K

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 101
作問者 : Cafe1942 / テスター : kazuppa sclara
お気に入りにしたユーザー ProblemId : 12268 / 自分の提出
問題文最終更新日: 2025-05-29 17:54:22
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
Math Cafe 1 (順位表) の他の問題:

Problem Statement

An $X$-sided die is a die that has $X$ faces and contains each of the non-negative integers from $1$ to $X$ exactly $1$ time. Each face is equally likely to come up.

You roll $N$ dice. The $i(1 \leq i \leq N)$-th die is an $A_i$-sided die. Find the probability that the largest value among the $N$ rolled values is exactly $K$, as a rational number $\text{mod} \ 998244353$.

What is a rational number $\text{mod} \ 998244353$? When the value is written as an irreducible fraction $\frac{P}{Q}$, for a rational number such that $Q \not \equiv 0 \pmod{998244353}$, there is a unique integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$, and $\frac{P}{Q}$ is represented by this $R$.

Constraints

  • $1 \leq N \leq 2 \times 10^{5}$
  • $1 \leq K \leq 998244352$
  • $1 \leq A_i \leq 998244352 (1 \leq i \leq N)$
  • All input values are integers.

Input

$N$ $K$
$A_1$ $A_2$  $\dots$ $A_N$

Output

Output the probability as a rational number $\text{mod} \ 998244353$.

Sample

Sample 1
Input
2 5
6 6
Output
748683265

When rolling $2$ dice with $6$ faces, the probability that the largest rolled value is exactly $5$ is $\frac{1}{4}$.

Sample 2
Input
1 1
1
Output
1

When rolling $1$ die with $1$ face, the probability that the largest rolled value is exactly $1$ is $1$.

Sample 3
Input
7 7
7 2 11 13 5 3 17
Output
479675858

The probability is $\frac{5}{77}$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。