問題一覧 > 通常問題

No.1939 Numbered Colorful Balls

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 24
作問者 : noya2 / テスター : tatyam 👑 hamamu tassei903
お気に入りにしたユーザー ProblemId : 7473 / 自分の提出
問題文最終更新日: 2022-05-11 00:32:36
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 343 (順位表) の他の問題:

Problem Statement

There are plenty of balls of every kind, where each ball is painted in exactly $1$ of the colors color $1,$ color $2,\dots$ and has exactly $1$ of the numbers $1,2,\dots$ written on it.

A row of balls arranged from left to right is called a good row of balls if it can be made empty by repeating the following operation.

  • Choose $i$ satisfying $1\le i\le M$.
  • Choose a place where $l_i$ horizontally consecutive balls all have color $l_i$ and the numbers written on them are $1,2,\dots ,l_i$ in order from the left, and remove them from the row.
  • If a gap is left in the row, close the gap.
  • Find the number of good rows of balls that can be formed by arranging $N$ balls, and print it modulo $998244353$.

    Constraints

  • All inputs are integers.
  • $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)$
  • Input

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

    Output

    Find the number of good rows of balls that can be formed by arranging $N$ balls, and print it modulo $998244353$.

    Sample

    Sample 1
    Input
    3 2
    1 2
    Output
    4

    Let $(i,j)$ denote a ball painted in color $i$ with the number $j$ written on it. The following $4$ rows are the good rows of balls that can be formed by arranging $3$ balls.

  • $(1,1),(1,1),(1,1)$
  • $(1,1),(2,1),(2,2)$
  • $(2,1),(1,1),(2,2)$
  • $(2,1),(2,2),(1,1)$
  • Sample 2
    Input
    100 1
    2
    Output
    512803529

    Find the answer modulo $998244353$.

    Sample 3
    Input
    55555 5
    5 55 555 5555 55555
    Output
    118151184

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