mayoko’s diary

プロコンとかいろいろ。

yukicoder No.336 門松列列

yukicoder
問題

No.336 門松列列 - yukicoder

解法

こういう会話があったので, 包除原理で解いてみました。

この問題は, 下の問題の部分問題です。
mayokoex.hatenablog.com

どうやら昔はめぐるちゃんに解説を任せていたらしいので, 今回はもうちょっと書こうと思います。

1 〜 N からなる順列 p を考えます。
ある配列 v があって, v に数 el がある場合, そしてその場合のみ, 順列 p について, p[el] < p[el+1] が成り立つような順列がいくつあるのかを考えます。

v が {a, b, c, ..., d} となっていたとすると, 区間 [0, a], [a+1, b], ... で順列は単調減少しています。
区間 [0, a], [a+1, b], ... で単調減少になるような順列の数は, C[N][a+1] * C[N-(a+1)][b-a] * ... となります。(C は combination です。)

ですが, 単に単調減少するだけだと, [0, a] で単調減少で, p[a] > p[a+1] となってしまい, また [a+1, b] も単調減少になる, というような場合を排除できていません。このような v の要素 el で p[el] > p[el+1] が成り立ってしまっているようなことを「違反」ということにすると, 先ほどの数え上げだけでは, 違反回数が 0 回"以上"のものを数えただけ, ということになります。

じゃあ違反回数が 0 回のものを数え上げるにはどうすれば良いかというと, 包除原理を使って,
(違反回数が 0 回以上の場合の数) - (違反回数が 1 回以上の場合の数) + (違反回数が 2 回以上の場合の数) - ...
というように計算していけば良いです。

違反回数が 1 回以上のものを数えるときは, 区間 [0, a] ではなく 区間 [0, b], [b+1, c], ... で単調減少している, とか 区間 [0, a], [a+1, c], ... で単調減少している, とか考えれば良いです。要するにどこか連続している区間を接合するわけです。

違反回数 2 回以上とかになると頭で考えるのは難しいですが, これを上手く計算するために dp を使います。

dp[cur][f] = (配列 v の cur 個目から先の要素で, 違反回数を 2 で割った余りが f であるような場合の数) とします。
dp の遷移としては, v のどこまで先の要素まで単調減少させるかを全列挙する感じです。v のどこまで先の要素を単調減少させるか決まれば, 違反回数の偶奇もわかります。

なんとなくこれで良いのですが, 実装どうするかでだいぶ悩んだのでそこについても少し書きます。

雰囲気はこんな感じです。
f:id:mayokoex:20160116110901j:plain

v の座標に合わせるのではなく, num に合わせて dp の cur を考えます。例えば dp[0][0] を考えるときは, 「今 v[0] にいる」と考えるのではなく, 「単調減少させる数列の数は num[0] or num[0]+num[1] or ... となっているような場所にいる」と考える感じです。v に合わせて考えると, 0 から v[0] までの処理をどうするかとか, v[M-1] から N-1 までの処理をどうするかとか考えないといけなくて面倒そうです。

const ll MOD = 1e9+7;

ll dp[1010][2];
ll C[2020][2020];
int M;
vector<int> length;

ll dfs(int cur, int f) {
    if (cur == M) return f==0 ? 1 : -1;
    ll& ret = dp[cur][f];
    if (ret >= 0) return ret;
    ret = 0;
    int sum = 0;
    for (int i = cur; i < M; i++) {
        sum += length[i];
        ll tmp = C[2*cur+sum][2*cur];
        int nf = f^((i-cur)&1);
        (tmp *= dfs(i+1, nf)) %= MOD;
        (tmp += MOD) %= MOD;
        ret += tmp;
    }
    ret %= MOD;
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    for (int i = 0; i < 2020; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) C[i][j] = (C[i-1][j-1]+C[i-1][j]) % MOD;
    }
    cin >> N;
    if (N <= 2) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 0; i < N; i+=2) length.push_back(min(2, N-i));
    M = length.size();
    memset(dp, -1, sizeof(dp));
    ll ans = dfs(0, 0);
    (ans *= 2) %= MOD;
    cout << ans << endl;
    return 0;
}