問題一覧 > 通常問題

No.1939 Numbered Colorful Balls

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : noya2noya2 / テスター : 👑 tatyamtatyam hamamuhamamu tassei903tassei903
6 ProblemId : 7473 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-11 00:32:36

問題文

色 $1,$ 色 $2,\dots$ の色のいずれか $1$ 色で塗られ、 $1,2,\dots$ の数字のうちいずれか $1$ つが書かれたボールがそれぞれたくさんあります。

左右一列に並んだボールの列が、以下の操作を繰り返して空の列にできるとき、 そのボールの列を良いボールの列とよびます。

  • $1\le i\le M$ を満たす $i$ を選ぶ。
  • 左右に連続する $l_i$ 個のボールの色が $l_i$ で、書かれた数字が左から順に $1,2,\dots ,l_i$ であるような箇所を選び、 それらを列から取り除く。
  • 列に間が空いたら、間を詰める。

    • $N$ 個のボールを並べてできる良いボールの列がいくつかあるかを求め、$998244353$ で割ったあまりを出力してください。

    制約

  • 入力はすべて整数
  • $1\le N\le 10^5$
  • $1\le M\le 10^2$
  • $1\le l_i\le N\ (1\le i\le M)$
  • $l_i\neq l_j\ (i\neq j)$

    • 入力

    $N\ M$
$l_1\ l_2\ \dots l_M$

    出力

    $N$ 個のボールを並べてできる良いボールの列がいくつかあるかを求め、$998244353$ で割ったあまりを出力してください。

    サンプル

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

    色 $i$ で塗られ、$j$ の数字が書かれたボールを $(i,j)$ と表します。 $3$ 個のボールを並べてできる良いボールの列は次の $4$ つです。

  • $(1,1),(1,1),(1,1)$
  • $(1,1),(2,1),(2,2)$
  • $(2,1),(1,1),(2,2)$
  • $(2,1),(2,2),(1,1)$

    • サンプル2
    入力
    100 1
2
    出力
    512803529

    $998244353$ で割ったあまりを求めてください。

    サンプル3
    入力
    55555 5
5 55 555 5555 55555
    出力
    118151184

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