yukicoder No.336 門松列列

やっと出来た…（1問前よりはマシ）

問題概要

長さNの1〜Nの数字が1つずつある数列でどの隣り合った3つの数字を選んでも門松列になっている数列は何通りあるか。1e9+7で割った余りを求めよ。

No.336 門松列列 - yukicoder

解法

終了後に解説見ました。「合ってるやん!!」と突っ込みました。nCmを前計算することを忘れていたんですね。

n=5の時、5の入る位置は

5 o o o o

o 5 o o o

o o 5 o o

o o o 5 o

o o o o 5

のどれかです。この時、oが3つ以上並んでいたらそのoの列は門松列列を満たしていなければなりません。

また、5を含んでも門松列を満たさなければいけないです。

しかし、これって左にoが1つしか無ければo 5 oは絶対に門松列を満たします。

左にoが2つであれば2つのうち大きい方を左側、小さい方を右側に持っていった1通り。

oが3つ以上であればその列自体が門松列列を満たす必要があります。また、oがx個あるとすると、各要素を(x-o+1)とすることでまた条件を満たす門松列列が出来ます。この時右端の2要素の上下関係が逆転します。つまりx個の門松列列の数の半分が左側に入り得る、ということになります。

n=4まではサンプルに入っているので、n=5からnの新しく入る位置をループで回しながら、右側の空きの個数の門松列列の通り数×左側の空きの個数の門松列列の個数×n個からの右側の個数の選び方をして、更に左右の空き個数が3個以上なら2で割った数字を毎回足してあげればOKです。割るときはフェルマーの小定理を用いて逆元を求めましょう。

//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;
}

感想

ここはサラッと流したかったのだけれども、三角形求める時点でミスが発覚して大幅タイムロス。今後活かせるからいいや。