問題一覧 > 通常問題

No.1554 array_and_me

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 57
作問者 : theory_and_metheory_and_me / テスター : shotoyooshotoyoo
7 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もしくは右上の雲マークをクリックしてアカウントを作成してください。