No.2941 Sigma Music Game Score Problem
レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 75
作問者 :
kazuppa
/ テスター :
Yoyoyo8128
yuusaan
hirayuu_yc
タグ : / 解いたユーザー数 75
作問者 :
kazuppa
/ テスター :
Yoyoyo8128
yuusaan
hirayuu_yc
問題文最終更新日: 2024-10-18 21:17:21
裏話
当時プ●●●でFCできなさ過ぎた悲しさのあまり、この問題ができました。
察してあげてください。ストーリー
音ゲーが上手い（と一部界隈では言われているらしい）kazuppa君は音ゲーが大好きで、Xでのつぶやきは競プロ関連か音ゲー関連になっているほどです。
そんな彼は、このあいだ新しい音ゲーを見つけました！問題文
このゲームの判定は「Perfect」「Miss」の二つのみです。
このゲームにおける各ノーツのスコアは次のように求められます。- 長さ $M+1$ となる正整数列 $S_0,S_1...S_{M}$ を用いる。はじめ、 $S_0$ は $0$ で初期化されている。
- $i$ 番目のノーツの判定が「Perfect」なら $S_i=S_{i-1}+1$ にする。
- $i$ 番目のノーツの判定が「Miss」なら $S_i=0$ にする。
- そして、このゲームでのスコアは $\displaystyle\sum_{i=1}^M {S_i}^2$ とする。
入力
入力は以下の形式で標準入力から与えられる。$M\ N$
$X_1\ \ X_2\ ...\ X_{N}$
制約
- $2\leq M\leq 10^{15}$
- $0\leq N\leq \min(10^6,M)$
- $X_i< X_{i+1} \ (1\leq i\leq N)$
- $1\leq X_1\ (1\leq N)$
- $X_{N}\leq M\ (1\leq N)$
- 入力はすべて整数
出力
総スコア $ \bmod{998244353}$ を一行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
5 2 1 3
出力
6
各ノーツにて $S_i$ は次のようになります。
$1$ノーツ目：Missノーツのため $S_1=0$ になる$2$ノーツ目：Missノーツじゃないため $S_2=S_1+1=1$ になる
$3$ノーツ目：Missノーツのため $S_3=0$ になる
$4$ノーツ目：Missノーツじゃないため $S_4=S_3+1=1$ になる
$5$ノーツ目：Missノーツじゃないため $S_5=S_4+1=2$ になる よって、答えは $0^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
総スコア $\bmod{998244353}$ で出力することに注意しましょう。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。