問題一覧 > 通常問題

No.1387 Mitarushi's Remodeling

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 9
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
2 ProblemId : 5798 / 出題時の順位表
問題文最終更新日: 2021-02-08 08:53:26

問題文

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

    Divide Card

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

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

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

    操作としてありえるのは$\ (N-1) \times (N-2) \times \cdots \times (N-K)\ $通りありますが、その全てにおいて操作後の$\ S\ $を足し合わせた値を求めてください。

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

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

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

    Mitarushi's Remodeling

    整数$\ N^\prime ,K^\prime\ $と$\ N^\prime\ $個の正の整数$\ M_1,M_2, \cdots ,M_{N^\prime}\ $が与えられます。
    「$\ N=N^\prime\ $かつ$\ 1 \leq K \leq K^\prime\ $かつ$\ 1\ $以上$\ N^\prime\ $以下の全ての整数$\ i\ $に対し$\ 1 \leq A_i \leq M_i\ $」が満たされるようなDivide Cardの入力は$\ K^\prime \times M_1 \times M_2 \times \cdots \times M_{N^\prime}\ $通りありますが、その全てに対してDivide Cardの答えを足し合わせた値を求めてください。

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

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

入力

$N^\prime\ \ K^\prime$
$M_1\ \ M_2\ \ \cdots \ \ M_{N^\prime}$

  • $1 \leq K^\prime < N^\prime \leq 5\times 10^5$
  • $1 \leq M_i \leq 10^9(1 \leq i \leq N^\prime)$
  • 入力は全て整数

出力

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

サンプル

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

Divide Cardの入力としてありえる$\ N,K,A_i\ $は$\ N=3,K=1,A_1=1,A_2=1,A_3=1\ $と$\ N=3,K=1,A_1=1,A_2=1,A_3=2\ $の$\ 2\ $通りあります。
前者の入力の場合を考えます。

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

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

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

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

$1\ $つ目の操作をした場合、$\ S\ $に$\ 1\times(1+1)\ $が加算され、$\ S=2\ $となります。
$2\ $つ目の操作をした場合、$\ S\ $に$\ (1+1)\times1\ $が加算され、$\ 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もしくは右上の雲マークをクリックしてアカウントを作成してください。