問題一覧 > 通常問題

No.2941 Sigma Music Game Score Problem

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 107
作問者 : kazuppa / テスター : Yoyoyo8128 yuusaan hirayuu_yc
0 ProblemId : 11335 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-18 21:17:21

裏話

当時プ●●●でFCできなさ過ぎた悲しさのあまり、この問題ができました。

察してあげてください。

ストーリー

音ゲーが上手い（と一部界隈では言われているらしい）kazuppa君は音ゲーが大好きで、Xでのつぶやきは競プロ関連か音ゲー関連になっているほどです。

そんな彼は、このあいだ新しい音ゲーを見つけました！

問題文

このゲームの判定は「Perfect」「Miss」の二つのみです。

このゲームにおける各ノーツのスコアは次のように求められます。

  • 長さ M+1M+1 となる正整数列 S0,S1...SMS_0,S_1...S_{M} を用いる。はじめ、 S0S_0 は 00 で初期化されている。
  • ii 番目のノーツの判定が「Perfect」なら Si=Si−1+1S_i=S_{i-1}+1 にする。
  • ii 番目のノーツの判定が「Miss」なら　Si=0S_i=0 にする。
  • そして、このゲームでのスコアは ∑i=1MSi2\displaystyle\sum_{i=1}^M {S_i}^2 とする。
kazuppa君は、総ノーツ数が MM 個の曲にチャレンジしました。

結果、Miss数は NN 個になり、 ii 番目のMissノーツは XiX_i 個目のノーツでした。

スコアをできるだけ早く知りたいkazuppa君のために、スコアを高速に求めるプログラムを書いてください。

ただし、kazuppa君は 998244352998244352 までの数しか知らないので、スコア  mod 998244353\bmod{998244353} で出力してください。

入力

入力は以下の形式で標準入力から与えられる。 
M NM\ N
X1  X2 ... XNX_1\ \ X_2\ ...\ X_{N}

制約

  • 2≤M≤10152\leq M\leq 10^{15}
  • 0≤N≤min⁡(106,M)0\leq N\leq \min(10^6,M)
  • Xi<Xi+1 (1≤i≤N)X_i< X_{i+1} \ (1\leq i\leq N)
  • 1≤X1 (1≤N)1\leq X_1\ (1\leq N)
  • XN≤M (1≤N)X_{N}\leq M\ (1\leq N)
  • 入力はすべて整数

出力

総スコア  mod 998244353 \bmod{998244353} を一行に出力してください。
最後に改行してください。

サンプル

サンプル1
入力
5 2
1 3
出力
6

各ノーツにて SiS_i は次のようになります。

11ノーツ目：Missノーツのため S1=0S_1=0 になる
22ノーツ目：Missノーツじゃないため S2=S1+1=1S_2=S_1+1=1 になる
33ノーツ目：Missノーツのため S3=0S_3=0 になる
44ノーツ目：Missノーツじゃないため S4=S3+1=1S_4=S_3+1=1 になる
55ノーツ目：Missノーツじゃないため S5=S4+1=2S_5=S_4+1=2 になる

よって、答えは 02+12+02+12+22 mod 998244353=60^2+1^2+0^2+1^2+2^2\bmod{998244353}=6 となります。

サンプル2
入力
5 5
1 2 3 4 5
出力
0

kazuppa君は下手なのかもしれません。

サンプル3
入力
5 0
出力
55

kazuppa君は天才なのかもしれません。

サンプル4
入力
19879 7
3843 7839 10932 14148 14863 15203 17416
出力
962728197

総スコア  mod 998244353\bmod{998244353} で出力することに注意しましょう。

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