結果

問題 No.336 門松列列
ユーザー fiordfiord
提出日時 2016-01-23 17:43:16
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 35 ms / 2,000 ms
コード長 888 bytes
コンパイル時間 1,332 ms
コンパイル使用メモリ 158,732 KB
実行使用メモリ 34,812 KB
最終ジャッジ日時 2024-06-12 01:12:08
合計ジャッジ時間 2,004 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

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