yukicoder : No.336 門松列列

これは★３でもいいかも。実装はNo.335より簡単だし…。
http://yukicoder.me/problems/933

問題

正整数Nが与えられる。
1～Nのpermutationのうち、どの連続する３要素を取っても門松列を成しているようなもの(門松列列)はいくつあるか。

解法

k要素の門松列列のうち、1値目より2値目が小さいものの数をF(k)とする。
1値目より2値目が小さいものと大きいものは同数あると考えると、求めたい値はF(N)*2である。

1～kのpermutation(門松列列とは限らない)のどこかに(k+1)を挿入し、1値目より2値目が小さい(k+1)要素の門松列列を作ることを考える。
(k+1)をx+1番目の要素となる位置に挿入することを考える。
先頭x個が偶数個かつ1値目より2値目が小さい門松列列で、末尾(k-x)個が1値目より2値目が大きい門松列列であれば、それらを連結してできる
[(x要素(偶数)からなる1値目より2値目が小さい門松列列),(k+1),((k-x)要素からなる1値目より2値目が大きい門松列列)]という形の数列は(k+1)要素の門松列列をなす。

よって偶数xに対し、F(k+1) += F(x)*F(k-x)*Comb(k,x)で足しこんでいけばF(k+1)を求められる。
(Combinationは、k要素中どのx個を(k+1)の手前に持ってくるか選ぶ選び方の分)

この問題の解としてはN=1,2の際は0と答えるが、以下の計算ではF(0)=F(1)=F(2)=1とおく点に注意。

ll N;
ll mo=1000000007;
const int CN=4001;
ll C[CN][CN];
ll dp[2300];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
	
	cin>>N;
	if(N<=2) return _P("0\n");
	
	dp[0]=dp[1]=dp[2]=1;
	dp[3]=2;
	for(i=3;i<=N-1;i++) for(x=0;x<=i;x+=2) (dp[i+1]+=C[i][x]*dp[x]%mo*dp[i-x])%=mo;
	
	cout<<dp[N]*2%mo<<endl;
	
}

まとめ

実装は単純。