TopCoder SRM 717 Div 2 Hard (Div1 Med): DerangementsStrikeBack

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

長さ の順列 であって、先頭 要素について が成立するようなものの総数を求めよ。

解説

Div2 では制約が小さいため、以下のように解くことができます。

「先頭 要素について である」事象の余事象を考えます。つまり、 を満たす要素が少なくとも つある状況です。

を満たす要素が 個ある順列の総数を考えます。これは 先頭 要素について を満たす順列の総数 と定義するとき、 と計算できます ( となる要素の場所が combination で計算でき、それを除いた状態を考えると再帰的に計算できる)。

よって、この問題の答えは、順列が 通りある中から、 「 を満たす要素が 個ある」場合を引いたものであるため、

と求められます。これは で動きます。

Div1 では であるため、まだ足りません。ここで、 AtCoder Regular Contest 009 C: 高橋君、24歳 - hogecoder と同じように、完全順列と同じような考察をすることにしましょう。 は 番目の要素に関して次のような場合分けをすることで求められます。

• 番目の要素が である (これは 通りあり、 番目の要素には何が来ても良いため、残りの数の並べ方は に等しい)
• 番目の要素が であって、 番目の要素が (これは 通りあり、 番目と 番目の要素についてはもう考慮する必要がないので、残りの数の並べ方は に等しい)
• 番目の要素が であって、 番目の要素が (これは 通りあり、残りの数の並べ方は に等しい)

以上を踏まえると、 となり、 で求められます。

ソースコード

Div2 (どうせ comb の配列を初期化しなくても動くだろうと思って出したら落ちたので、初期化は大事です)

class DerangementsDiv2 {
    public:
    ll comb[110][110];
    ll fact[110], dp[110];
    int count(int n, int m) {
        memset(comb, 0, sizeof(comb));
        fact[0] = comb[0][0] = 1;
        for(int i=1; i<=n+m; i++) {
            fact[i] = (fact[i-1] * i) % MOD;
            comb[i][0] = 1;
            for(int j=1; j<=i; j++) {
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
            }
        }

        for(int i=0; i<=m; i++) {
            dp[i] = fact[n+i];
            for(int k=1; k<=i; k++) {
                ll sub = (comb[i][k] * dp[i-k]) % MOD;
                dp[i] = (dp[i] - sub + MOD) % MOD;
            }
        }

        return dp[m];
    }
};

Div1

class DerangementsStrikeBack {
    public:
    ll dp[100010];
    int count(int n, int m) {
        dp[0] = 1, dp[1] = n;
        for(int i=2; i<=m; i++) {
            dp[i] = ((n+i-1) * dp[i-1] + (i-1) * dp[i-2]) % MOD;
        }

        ll ans = 0;
        for(int i=1; i<=m; i++) {
            ans ^= dp[i];
        }
        return ans;
    }
};