mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #315 (Div. 1) B. Symmetric and Transitive

Codeforces Round #315 (Div. 1)に参加しました。A しか解けずちーん。
調べてみたらわかったんですが, 僕はCodeforces の Div. 1 で 1 回しかレートを上げたことが無いようです(Div.1 Div.2 合同のラウンドで上げてる)。

解法

問題文中で触られている同値関係(equivalence relation)の後半2つの特徴(symmetric, transitive)がどういう意味を持つのかを考えます。

まず symmetric の方は, 例えば x-y の関係があるなら y-x の関係もあるよね, ということです。これをグラフに当てはめて考えると, x -> y という有向辺があるなら, y -> x という有向辺もあるよね, ということです。つまり, 関係性をグラフで考えると, 無向グラフで考えれば良い, ということです。

次に transitive の方は, 上で示したグラフは, 複数のクリークで出来ている, ということを示しています。例えば 3 つの頂点の間で同値関係が成り立っているとすると,
x - y, y - z, z - x で二項関係がありますが, これは x, y, z でクリークを形成しています。

ということで, この問題は,

「n 頂点のうち全部は使わないようにしてクリークをいくつか作る。このようなクリークの作り方は何通りあるか。」

という問題に落とし込めます。
f:id:mayokoex:20150811143131j:plain
例えば上の図(表のセルの中に丸がついてると対応する頂点と頂点が無向辺で繋がれていることを示す)では a は a 単体でクリークに, b, c は 2 つの頂点で構成されるクリークになっていて, d はなにとも繋がっていない頂点です。
この状態では a, b, c は reflexive (反射律) が成り立っているのはいいんですが d には反射律が成り立っていないので題意のグラフの一つです。こんな感じのの個数を求められれば良いと。

大まかな方針は n 個中何個の頂点が何らかのクリークに属するかを i として, i = 0 から i = n-1 まで走らせてその和を取る, という方針で行きます。各 i についてそこそこ少ない計算量で 「合計で頂点数が i になるようなクリークのわけかた」が求められれば勝ちです。
例えば上の図では n = 4 で i = 3 です。 i = 3 となるようなクリークの作り方には他にも例えば a-a, b-b, c-c だけが二項関係を持つものとかもありますね。

上ではクリークとか書きましたが, 結局のところ大事なのは, i の分け方だけです。例えば選ばれた 3 つの頂点を a, b, c として,
3 = 1+2
と書けば上の図ではクリークは {a} と {b, c} の 2 つにわかれていることがわかりますし,
3 = 1+1+1
と書けば上の図ではクリークは {a} と {b} と {c} の 3 つにわかれていることがわかります。

そこで, dp[i][j] = (i をぴったり j 個の数に分けるような場合の数)とします。ちょっと注意ですがこれは蟻本に書いてある分割数とは少し違います(蟻本では 1+1+2 と 1+2+1 を区別していないがこちらの dp はそれを区別する)。
これが求まれば「合計で頂点数が i になるようなクリークのわけかた」は dp[i][0] から dp[i][i] の和で求められますね。

で, この値は, i-1 の時点ですでに j 個に値を分割しているか, i-1 の時点では j-1 個にしか値がわかれていないかに場合分けすると,
dp[i][j] = dp[i-1][j-1] + dp[i-1][j] * j

で求めることが出来ます。


途中で mo2[] とかいうのを作っていますが全く関係無いです(考えの途中で出てきた)。

const int MAXN = 4020;
const ll MOD = 1e9+7;

ll mo2[MAXN];
ll nCr[MAXN][MAXN];
ll dp[MAXN][MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    mo2[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        mo2[i] = (mo2[i-1] * 2) % MOD;
    }
    for (int i = 0; i < MAXN; i++) {
        nCr[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            nCr[i][j] = (nCr[i-1][j-1] + nCr[i-1][j])%MOD;
        }
    }
    dp[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        dp[i][i] = dp[i][1] = 1;
        for (int j = 2; j < i; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j] * j;
            dp[i][j] %= MOD;
        }
    }
    ll ans = 1;
    for (int i = 1; i < n; i++) {
        ll sum = 0;
        for (int j = 1; j <= i; j++) sum += dp[i][j];
        sum %= MOD;
        ans += (sum*nCr[n][i]) % MOD;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}