問題一覧 > 通常問題

No.1939 Numbered Colorful Balls

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : noya2noya2 / テスター : tassei903tassei903 hamamuhamamu tatyamtatyam
4 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もしくは右上の雲マークをクリックしてアカウントを作成してください。