けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2935 赤黒そーるじぇむ (RUPC 2019 day3-F)

AOJ RUPC 数え上げ問題 グラフ・盤面・数列の個数の数え上げ グラフ 包除原理 包除原理:対称性 二項係数 式変形 二項定理 ある量を固定して考える

楽しい！！！好き！！！

問題へのリンク

問題概要

N 頂点のグラフを作って各頂点に赤黒に色をつけたい。そのような 2^{N} × 2^{\frac{N(N-1)}{2}} 通りの方法のうち、以下の条件を満たすような方法が何通りあるか M で割ったあまりを求めよ。

  • どの赤い頂点も、なんらかの黒い頂点とつながっている
  • どの黒い頂点も、なんらかの赤い頂点とつながっている
  • グラフは連結でなくても良い

制約

考えたこと

メッチャ楽しそう！！！！！
かなり好きなタイプの問題で、見るからに包除原理だなという感じの雰囲気。

とりあえずは、赤を R 個、黒を B 個とするときについて考えて見る。まず

  • そのような赤頂点を選ぶ: C(N, R) 通り
  • 赤頂点同士を結ぶ辺はあってもなくてもよい: 2^{\frac{R(R-1)}{2}} 通り
  • 黒頂点同士を結ぶ辺はあってもなくてもよい: 2^{\frac{B(B-1)}{2}} 通り

という状態になっていて、これらはあとで掛け算することにすればよい。そうすると問題は

左側の頂点数が R 個、右側の頂点数が B 個あるような二部グラフのうち、どの頂点も孤立点とはなっていないものが何通りあるか

を数え上げる問題になる。すごく一般性のある設定になっていて好き！！！！！！！！！！！！！！

ここからはまさに包除原理が適用できる状態になっていて、

  • f(r, b) := 左側のうち r 個が使われていなくて、右側のうち b 個以上が使われていない場合の数 ( C(R, r) × C(B, b) × 2^{(R-r)(B-b)} 通りになる)

として、 r+b が偶数なら足し、奇数なら引くような包除原理をしたくなる。しかしこのままでは O(RB) 通りの計算を行うことになる。その調子で R = 0, 1, \dots, N を全部試すとなると、合計で O(N^{3}) の計算時間を要してしまう。このままでは間に合わない。

大きく 2 つの解法を考えた。

解法 1: 片方は固定してしまう

beet さんの記事にも書いてある方針で考えてみる。いわゆる「条件付き包除原理」という考え方。

包除原理を赤黒両方で考えるのではなく、赤い方のみで考えてみる。すなわち

  • 赤頂点のうち r 個が使われない
  • 黒頂点はすべて使われる

というものが数え上げられればよい。これは実は簡単に数え上げることができて、

  • 各黒頂点について、赤頂点の残り R-r 個のうちの少なくとも 1 つに接続している

というようなものを数え上げればよいので、 C(R, r) × (2^{R-r}-1)^{B} 通りとなる。よってこれを

  • r が偶数のときは足し
  • r が奇数のときは引き

をすれば求められる。

#include <iostream>
#include <vector>
using namespace std;

int N, MOD;
const int MAX = 210000;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    cin >> N >> MOD;
    COMinit();
    long long res = 0;
    for (int R = 0; R <= N; ++R) {
        int B = N-R;
        
        // 包除原理
        long long tmp = 0;
        for (int r = 0; r <= R; ++r) {
            long long tmp2 = COM(R, r) * modpow((modpow(2LL, R-r, MOD) - 1 + MOD) % MOD, B, MOD) % MOD;
            if (r & 1) tmp = (tmp - tmp2 + MOD) % MOD;
            else tmp = (tmp + tmp2) % MOD;
        }
        
        // 自由度
        long long fac = COM(N, R) * modpow(2LL, R*(R-1)/2 + B*(B-1)/2, MOD) % MOD;
        tmp = (tmp * fac) % MOD;
        
        // 合計
        res = (res + tmp) % MOD;
    }
    cout << res << endl;
}

解法 2: 二項定理を駆使しながら二項係数計算を頑張る

赤頂点についても黒頂点についても両方ともまとめて包除原理を適用した式

  • \sum_{r = 0}^{R} \sum_{b = r}^{B} (-1)^{r + b} C(R, r) × C(B, b) × 2^{(R-r)(B-b)}

を気合いで式計算する。二項定理を使えそうな雰囲気があるので、そうなるように式変形して行く。まず、 2^{(R-r)(B-b)} のところがちょっと嫌なので変数変換して

  • r ← R - r
  • b ← B - b

による変数変換を施すと

  • \sum_{r = 0}^{R} \sum_{b = r}^{B} (-1)^{R+B -r-b} C(R, r) × C(B, b) × 2^{rb}

となる。ちょっとは見やすくなった。さらに式変形を続けて、

\sum_{r = 0}^{R} \sum_{b = r}^{B} (-1)^{R+B -r-b} C(R, r) × C(B, b) × 2^{rb}
= (-1)^{R+B} \sum_{r = 0}^{R} \sum_{b = r}^{B} (-1)^{r+b} C(R, r) × C(B, b) × 2^{rb}
= (-1)^{R+B} \sum_{r = 0}^{R} (-1)^{r} C(R, r) \sum_{b = r}^{B} C(B, b) × (-2^{r})^{b}

最後の式を見ると、二項定理より

\sum_{b = r}^{B} C(B, b) × (-2^{r})^{b} = (1 - 2^{r})^{B}

とまとめられる。よって求めたい式は

(-1)^{R+B} \sum_{r = 0}^{R} (-1)^{r} (1 - 2^{r})^{B}

となる。実はもう少しよく眺めると、解法 1 で導いた式と同一になっていることがわかる。