問題一覧 > 通常問題

No.1387 Mitarushi's Remodeling

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
3 ProblemId : 5798 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-17 22:55:15

問題文

ある日、ミツバチ君は以下のような問題を思いつきました。

    Divide Card

    カードが N 枚重なった山が最初一つあり、この山の上から i 番目のカードには Ai という整数が書かれています。
    また、あなたは変数 S を持っており、現在は S=0 です。

    あなたは今からちょうど K 回、以下の操作を繰り返します。ここで 1K<N が成立しています。

      カードを Z  (2Z) 含む山を一つ選び、これを P とします。 P の上から t  (1tZ1) を順序を保って分割した山を Q とし、残った Zt 枚の山を新しく P とします。
      分割が終了した時点で P が含むカードに書かれた数字の総和を X  Q が含むカードに書かれた数字の総和を Y として、 S  X×Y を加算します。

    操作としてありえるのは (N1)×(N2)××(NK) 通りありますが、その全てにおいて操作後の S を足し合わせた値を求めてください。

    ただし、2 つの K 回の操作が異なるとは、i 回目の操作後に以下が成り立つような整数 i(1jK) が存在することとします。

      一方ではもともと上から l 番目にあったカードと m 番目にあったカードが同じ山にあり、もう一方では同じ山にないような整数 l,m(1l<mN) が存在する。

しかし、ミタルシ君にとってこれは簡単すぎたので、以下のような変更がなされました。

    Mitarushi's Remodeling

    整数 N,K  N 個の正の整数 M1,M2,,MN が与えられます。
     N=N かつ 1KK かつ 1 以上 N 以下の全ての整数 i に対し 1AiMi 」が満たされるようなDivide Cardの入力は K×M1×M2××MN 通りありますが、その全てに対してDivide Cardの答えを足し合わせた値を求めてください。

    ただし、答えは大きくなることがあるので、 998244353 で割った余りを出力してください。

Mitarushi's Remodelingを解いてください。

入力

N  K
M1  M2    MN

  • 1K<N5×105
  • 1Mi109(1iN)
  • 入力は全て整数

出力

Mitarushi's Remodelingの答えを出力し、最後に改行してください。 998244353 で割った余りを出力することに注意してください。

サンプル

サンプル1
入力
3 1
1 1 2
出力
11

Divide Cardの入力としてありえる N,K,Ai  N=3,K=1,A1=1,A2=1,A3=1  N=3,K=1,A1=1,A2=1,A3=2  2 通りあります。
前者の入力の場合を考えます。

最初の山にある重なった 3 枚のカードを上から X,Y,Z とします( X,Y,Z にそれぞれ A1,A2,A3 が書かれている)。

1 回目の操作においては以下の 2 通りが考えられます。

・山を X からなる山と、 Y,Z からなる山の 2 つに分割する。
・山を X,Y からなる山と、 Z からなる山の 2 つに分割する。

ここで、1 つめの操作後において Y,Z からなる山は上に Y があることに注意してください。
また、 X,Z からなる山と Y からなる山の 2 つに分割する操作はできないことにも注意してください。

1 つ目の操作をした場合、 S  1×(1+1) が加算され、 S=2 となります。
2 つ目の操作をした場合、 S  (1+1)×1 が加算され、 S=2 となります。

これより、この入力の場合のDivide Cardの答えは 2+2=4 です。

同様に考えると、もう一方の入力の場合のDivide Cardの答えは 7 であることが分かります。
よって、Mitarushi's Remodelingの答えは 4+7=11 です。

サンプル2
入力
7 6
20 21 2 10 2 11 76
出力
249962858

 2021 年の 2  10 日と 2  11 日に行われる高校入試を経て灘校 76 回生が入学します。
中学からいる「在来」に対し、「新高」と呼ばれます。

サンプル3
入力
10 7
31415 92653 58979 32384 62643 38327 95028 84197 16939 93751
出力
666468393

 998244353 で割った余りを出力してください。

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