問題一覧 > 通常問題

No.1554 array_and_me

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

問題文

正の整数 N,K と長さ N の正の整数の列 A1,A2,…,AN が与えられます．

長さ N の配列 z=[z1,z2,…,zN] の全要素を 0 に初期化し，以下の操作を K 回行います．

1. 整数 i∈{1,2,…,N} をランダムに選ぶ． ただし，i が選ばれる確率は Ai∑i=1NAi であり，操作ごとに試行は独立である．
2. 選ばれた i について，zi←zi+1 と更新する．

長さ N の非負整数配列全体からなる集合を S とし，x∈S に対して上記の操作の終了後 z=x となる確率を f(x) とします．
maxx∈Sf(x) を計算して下さい．

ただし，maxx∈Sf(x) はある既約分数 PQ として表せること， R×Q≡P (mod 998244353) かつ 0≤R<998244353 を満たす整数 R が 一意に定まることが問題の制約より証明できますので，この R を出力して下さい．

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

入力

入力の1行目は次の通りです． 
T
そして，T 個のテストケースがそれぞれ以下の形式で続きます． 
N K
A1A2…AN

  • 入力は全て整数
  • 1≤T≤100
  • 1≤N≤105
  • 1≤K≤105
  • 1≤Ai≤103
  • 全テストケースにおける N の和は 105 以下である．
  • 全テストケースにおける K の和は 105 以下である．

    • 出力

    各行に 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)=14，x=[1,1] のとき f(x)=12，x=[0,2] のとき f(x)=14 であり，それ以外の x∈S については f(x)=0 です． よって，maxx∈Sf(x)=12 です．

  • 2つ目のテストケースの説明
    • x=[1,0,0] のとき f(x)=14，x=[0,1,0] のとき f(x)=38，x=[0,0,1] のとき f(x)=38 であり，それ以外の x∈S については f(x)=0 です． よって，maxx∈Sf(x)=38 です．

  • 3つ目のテストケースの説明はありません．

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