問題一覧 > 通常問題

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もしくは右上の雲マークをクリックしてアカウントを作成してください。