問題一覧 > 通常問題

No.2941 Sigma Music Game Score Problem

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 109
作問者 : kazuppa / テスター : Yoyoyo8128 yuusaan hirayuu_yc
お気に入りにしたユーザー ProblemId : 11335 / 自分の提出
問題文最終更新日: 2026-10-19 10:20:12
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 450 (順位表) の他の問題:

Behind the Scenes

This problem was born out of my sheer sadness at being unable to get an FC on Pro●●● at the time.

Please take pity on me.

Story

Kazuppa, who is good at rhythm games (or so some circles apparently say), loves rhythm games so much that his posts on X are all about either competitive programming or rhythm games.

The other day, he found a new rhythm game!

Problem Statement

This game has only two judgments: "Perfect" and "Miss".

The score for each note in this game is determined as follows.

  • Use a sequence of positive integers $S_0,S_1...S_{M}$ of length $M+1$. Initially, $S_0$ is initialized to $0$.
  • If the judgment of the $i$-th note is "Perfect", set $S_i=S_{i-1}+1$.
  • If the judgment of the $i$-th note is "Miss", set $S_i=0$.
  • The score in this game is then $\displaystyle\sum_{i=1}^M {S_i}^2$.
Kazuppa challenged a song with a total of $M$ notes.

As a result, the number of Misses was $N$, and the $i$-th Miss note was note number $X_i$.

Kazuppa wants to know his score as soon as possible, so write a program that computes the score quickly.

However, Kazuppa only knows numbers up to $998244352$, so output the score $\bmod{998244353}$.

Input

The input is given from standard input in the following format. 
$M\ N$
$X_1\ \ X_2\ ...\ X_{N}$

Constraints

  • $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)$
  • $1\leq X_1\ (1\leq N)$
  • $X_{N}\leq M\ (1\leq N)$
  • All inputs are integers.

Output

Output the total score $ \bmod{998244353}$ on one line.
Print a newline at the end.

Sample

Sample 1
Input
5 2
1 3
Output
6

$S_i$ at each note is as follows.

Note $1$: it is a Miss note, so $S_1=0$
Note $2$: it is not a Miss note, so $S_2=S_1+1=1$
Note $3$: it is a Miss note, so $S_3=0$
Note $4$: it is not a Miss note, so $S_4=S_3+1=1$
Note $5$: it is not a Miss note, so $S_5=S_4+1=2$

Therefore, the answer is $0^2+1^2+0^2+1^2+2^2\bmod{998244353}=6$.

Sample 2
Input
5 5
1 2 3 4 5
Output
0

Kazuppa might not be very good.

Sample 3
Input
5 0
Output
55

Kazuppa might be a genius.

Sample 4
Input
19879 7
3843 7839 10932 14148 14863 15203 17416
Output
962728197

Note that the total score must be output $\bmod{998244353}$.

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