結果

問題 No.336 門松列列
ユーザー fiordfiord
提出日時 2016-01-23 17:43:16
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 35 ms / 2,000 ms
コード長 888 bytes
コンパイル時間 1,264 ms
コンパイル使用メモリ 145,060 KB
実行使用メモリ 33,908 KB
最終ジャッジ日時 2023-09-02 18:45:02
合計ジャッジ時間 2,273 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
33,860 KB
testcase_01 AC 12 ms
33,908 KB
testcase_02 AC 12 ms
33,776 KB
testcase_03 AC 12 ms
33,744 KB
testcase_04 AC 35 ms
33,760 KB
testcase_05 AC 12 ms
33,792 KB
testcase_06 AC 15 ms
33,800 KB
testcase_07 AC 20 ms
33,856 KB
testcase_08 AC 26 ms
33,780 KB
testcase_09 AC 34 ms
33,736 KB
testcase_10 AC 34 ms
33,740 KB
testcase_11 AC 35 ms
33,868 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//0,0,4,10,32,122,544,2770
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[2020][2020];
ll ans[2020];
const int mod=1000000007;
int mdpow(ll a){
	int n=mod-2;
	ll ret=1;
	while(n){
		if(n&1)	ret=(ret*a)%mod;
		a=(a*a)%mod;
		n>>=1;
	}
	return ret;
}
int main(){
	int n;	cin>>n;
	dp[0][0]=1;
	for(int i=1;i<2020;i++){
		for(int j=0;j<=i;j++){
			dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%mod;
		}
	}
	if(n<3){
		cout<<0<<endl;
		return 0;
	}
	ll md2=mdpow(2);
	ans[0]=ans[1]=1;
	ans[2]=2;	ans[3]=4;	ans[4]=10;
	for(int i=5;i<=n;i++){//i個の順列。iを除いた0〜(i-1)までの順列を利用。
		for(int right=0;right<i;right++){
			int left=i-1-right;
			ll multi=(((ans[left]*ans[right])%mod)*dp[i-1][left])%mod;
			if(right>=2)	multi=(multi*md2)%mod;
			if(left>=2)	multi=(multi*md2)%mod;
			ans[i]=(ans[i]+multi)%mod;
		}
	}
	cout<<ans[n]<<endl;
	return 0;
}
0