問題一覧 > 通常問題

No.3145 Astral Parentheses Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 55
作問者 : Nauclhlt🪷 / テスター : 👑 p-adic naniwazu
6 ProblemId : 12058 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-05-15 08:30:21

ストーリー

nauclhltくんはロマンチックな括弧列を思いつきました!

問題文

文字列 $X$ が星括弧列であるとは、次を満たすことをいいます。

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

正整数 $N$ が与えられるので、長さ $N$星括弧列として考えられるものはいくつあるかを求めてください。
答えは非常に大きくなることがあるので、$M$ (入力で与えられる正整数) で割った余りを求めてください。

入力

$N\ M$
  • $1\leq N\leq 1500$
  • $2\leq M\leq 10^9$
  • $N, M$ は整数

出力

長さ $N$ の星括弧列として考えられるものの個数を $M$ で割った余りを $r$ として、次の形式で1行に出力してください。

$r$

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

サンプル

サンプル1
入力
6 2
出力
1

長さが $6$ である星括弧列(*)(*)(*(*))((*)*)の $3$ 個あります。よって $3$ を $2$ で割った余りである1が答えです。

ここで、$M$ が素数とは限らないことに注意してください。

サンプル2
入力
4 998244353
出力
0

長さが $4$ である星括弧列は存在しません。

サンプル3
入力
1500 998244353
出力
201238254

この例では、$998244353$ で割った余りを出力します。

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