問題一覧 > 通常問題

No.1554 array_and_me

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : theory_and_metheory_and_me / テスター : shotoyooshotoyoo
6 ProblemId : 5031 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-18 21:59:31

問題文

正の整数 $N, K$ と長さ $N$ の正の整数の列 $A_1, A_2, \ldots, A_N$ が与えられます.

長さ $N$ の配列 $z = [z_1, z_2, \ldots, z_{N}]$ の全要素を 0 に初期化し,以下の操作を $K$ 回行います.

1. 整数 $i \in \{1, 2, \ldots, N \}$ をランダムに選ぶ. ただし,$i$ が選ばれる確率は $\frac{A_i}{\sum_{i=1}^{N}A_i}$ であり,操作ごとに試行は独立である.
2. 選ばれた $i$ について,$z_i \leftarrow z_i + 1$ と更新する.

長さ $N$ の非負整数配列全体からなる集合を $S$ とし,$x \in S$ に対して上記の操作の終了後 $z = x$ となる確率を $f(x)$ とします.
$\max_{x \in S} f(x)$ を計算して下さい.

ただし,$\max_{x \in S} f(x)$ はある既約分数 $\frac{P}{Q}$ として表せること, $R \times Q \equiv P \ (\mathrm{mod}\ 998244353)$ かつ $0 \leq R < 998244353$ を満たす整数 $R$ が 一意に定まることが問題の制約より証明できますので,この $R$ を出力して下さい.

テストケースが $T$ 個与えられるので,それぞれを解いてください.

入力

入力の1行目は次の通りです.
$T$
そして,$T$ 個のテストケースがそれぞれ以下の形式で続きます.
$N$ $K$
$A_1 A_2 \ldots A_N$

  • 入力は全て整数
  • $1 \leq T \leq 100$
  • $1 \leq N \leq 10^5$
  • $1 \leq K \leq 10^5$
  • $1 \leq A_i \leq 10^3$
  • 全テストケースにおける $N$ の和は $10^5$ 以下である.
  • 全テストケースにおける $K$ の和は $10^5$ 以下である.
  • 出力

    各行に $R$ の値を出力してください. 最後に改行してください.

    サンプル

    サンプル1
    入力
    3
    2 2
    1 1
    3 1
    2 3 3
    5 10
    31 41 59 26 53
    
    出力
    499122177
    623902721
    484466660
    

  • 1つ目のテストケースの説明
  • $x = [2, 0]$ のとき $f(x) = \frac{1}{4}$,$x = [1, 1]$ のとき $f(x) = \frac{1}{2}$,$x = [0, 2]$ のとき $f(x) = \frac{1}{4}$ であり,それ以外の $x \in S$ については $f(x) = 0$ です. よって,$\max_{x \in S} f(x) = \frac{1}{2}$ です.

  • 2つ目のテストケースの説明
  • $x = [1, 0, 0]$ のとき $f(x) = \frac{1}{4}$,$x = [0, 1, 0]$ のとき $f(x) = \frac{3}{8}$,$x = [0, 0, 1]$ のとき $f(x) = \frac{3}{8}$ であり,それ以外の $x \in S$ については $f(x) = 0$ です. よって,$\max_{x \in S} f(x) = \frac{3}{8}$ です.

  • 3つ目のテストケースの説明はありません.
  • 提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。