問題一覧 > 通常問題

No.3043 括弧列の数え上げ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 55
作問者 : Nauclhlt🪷 / テスター : eiram Blue_S naniwazu
2 ProblemId : 11808 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-09 01:40:52

ストーリー

eiramくんは対応が取れた括弧列を愛していますが、()()()よりも((()))の方が価値が高いと考えています。
ある長さの対応が取れた括弧列にeiramくんはどれだけ価値を感じるでしょうか？

問題文

ある文字列$X$が対応が取れた括弧列であるとは、次を満たすことをいいます。(これは競技プログラミングの問題文でよく見られる定義と同じです)

  • $X$に連続部分文字列として含まれる()を削除する操作を0回以上繰り返して$X$を空文字列とすることができる

例えば()(())や()()()()は対応が取れた括弧列ですが、))((や)()()(などは対応が取れた括弧列ではありません。

ある対応が取れた括弧列$T$に対して、次の手続きを行った後の$x$の値を$f(T)$とします。

  • はじめ、$S$を空集合、$x=0$として、$i=1, 2, \cdots, N$の順に次を行う
    • $T_i=$(ならば、$S$に$i$を追加する
    • $T_i=$)ならば、「$T$の開区間$(j, i)$を取り出した文字列が対応が取れた括弧列」を満たす$j(1\leq j\lt i)$を$S$から取り除き、その後$x$に$S$の要素数を加算する

    • 例えば、$f($()(())$)=1, f($()()()$)=0$です。

    正整数$N$が与えられるので、長さ$N$の対応が取れた括弧列$S$として考え得るすべての文字列に対する$f(S)$の総和を求めてください。
    答えは非常に大きくなることがあるので、$998244353$で割った余りを求めてください。

    文字列に関する表記 ある文字列$A$について、$A$の長さを$|A|$としたとき、$A_i(1\leq i\leq |A|)$で$A$の$i$番目の文字を表します。

    入力

    $N$
    • $1\leq N\leq 2000$
    • 入力はすべて整数

    出力

    $f(S)$の総和を$998244353$で割った余りを$r$として、次の形式で1行に出力してください。

    $r$

    最後に改行してください。

    サンプル

    サンプル1
    入力
    2
    出力
    0

    長さが2である対応が取れた括弧列は()のみです。$f($()$)=0$なので、0を出力します。

    サンプル2
    入力
    4
    出力
    1

    長さが4である対応が取れた括弧列は(())と()()の2つです。$f($(())$)=1$, $f($()()$)=0$より、1を出力します。

    サンプル3
    入力
    11
    出力
    0

    長さが11である対応が取れた括弧列は存在しません。

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