結果

問題 No.3145 Astral Parentheses Sequence
ユーザー 沙耶花
提出日時 2025-05-16 21:57:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 897 bytes
コンパイル時間 4,303 ms
コンパイル使用メモリ 250,320 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-16 21:57:54
合計ジャッジ時間 6,346 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘mint get(int, int)’:
main.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
   40 | }
      | ^

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000005
#define Inf64 4000000000000000001LL

mint dp[1600][3];
bool f[1600][3];
mint get(int x,int k){
	if(f[x][k])return dp[x][k];
	if(x<0)return 0;
	f[x][k] = true;
	if(k==0){
		if(x==0)return dp[x][k] = 1;
		return dp[x][k] = get(x-2,2);
	}
	if(k==1){
		if(x==0)return dp[x][k] = 1;;
		mint res = 0;
		for(int i=1;i<=x;i++){
			res += get(i,0) * get(x-i,1);
		}
		return dp[x][k] = res;
	}
	if(k==2){
		if(x==0)return 0;
		if(x==1)return dp[x][k] = 1;
		mint res = 0;
		for(int i=1;i<=x;i++){
			res += get(i,0) * get(x-i,2);
			res += get(i,0) * get(x-i-1,1);
		}
		return dp[x][k] = res;
	}
		
}
int main(){
	
	int n,m;
	cin>>n>>m;
	mint::set_mod(m);
	cout<<get(n,1).val()<<endl;
	
	return 0;
}
0