問題一覧 > 通常問題

No.3043 括弧列の数え上げ

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

ストーリー

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

問題文

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

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

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

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

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

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

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

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

    入力

    NN
    • 1≤N≤20001\leq N\leq 2000
    • 入力はすべて整数

    出力

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

    rr

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

    サンプル

    サンプル1
    入力
    2
    出力
    0

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

    サンプル2
    入力
    4
    出力
    1

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

    サンプル3
    入力
    11
    出力
    0

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

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