SRM 672 div1 med:AlmostEulerianGraph

問題

解法

CodeForces に上がっていた解説を参考にしました。codeforces.com

問題を簡単化していきます。

前提として, Eulerian Graph は, 「連結でありかつすべての頂点の次数が偶数であるようなグラフ」, almost Eulerian Graph は「連結でありかつ２つだけ頂点の次数が奇数であるような点が存在するようなグラフ」であることに注意します。

まず, almost Eulerian Graph ではなく, Eulerian Graph の数 En を求めれば, あとは「n 個の頂点の中から 2 つ選んでそれらの間に辺があれば取り除き, なければ付け加える」という操作をすることにより, Eulerian Graph でない almost Eulerian Graph を作ることが出来ます。また当然のことながら, Eulerian Graph に何もしないことにより, Eulerian Graph を作ることが出来ます。
n 個の頂点の中から 2 つ選ぶ方法は nC2 通りあるので, 結局求める答えは (nC2 + 1) * En となります。

ということで, En を求めたいのですが, その前に「すべての頂点の次数が偶数であるようなグラフ(連結とは言っていない)」の数 Dn を求めます。
実は Dn = pow(2, (n-1)(n-2)/2) で求められます。
一つの頂点だけ除いて残りの n-1 個の頂点で適当に辺を結びます。辺の候補は (n-1)(n-2)/2 通りあるので, 辺の結び方は pow(2, (n-1)(n-2)/2) だけあります。ここで, さっき取り除いた一つの頂点を, n-1 個の頂点それぞれに次のような規則で辺を結んだり結ばなかったりします。
・頂点の次数が奇数なら辺を結ぶ
・頂点の次数が偶数なら辺を結ばない
すると, n-1 個の頂点の次数はすべて偶数になります。また, すべての頂点の次数の和は 2 * (辺の数) になることが知られているので, 最初に取り除いた頂点の次数も偶数になります。このようにして構成したグラフはすべてバラバラになるので, Dn = pow(2, (n-1)(n-2)/2) になるわけです。

En を求めていきます。

En は, 「連結でなく, すべての頂点の次数が偶数であるようなグラフ」の数 Rn を用いて, En = Dn - Rn と書くことが出来ます。そこで, Rn を求めていきましょう。

例えば, 頂点 0 は k (1 <= k <= n-1) 個の連結した頂点を持つとしましょう。この場合の数は, n-1 個の頂点から k-1 個を選ぶことになるので (n-1) C (k-1) です。これが連結でかつ次数が偶数でないといけないですが, この場合の数は Ek と表せます。残りの n-k 頂点は次数が偶数で, この場合の数は D[n-k] です。よって, En は, Dn からこれらの積を引いた値になります。

得た知見

連結成分を考慮する数え上げでは頂点 0 にくっつく連結成分がいくつかで場合分けするのが典型らしい
それを知っていれば「全体を考える」 -> 「余事象」という発想も出てこなくもないかなぁ

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

int nCr[MAXN][MAXN];
ll E[MAXN];
ll D[MAXN];

ll pow_mod(ll n, ll p) {
    if (p == 0) return 1;
    if (p == 1) return n;
    if (p%2) return (pow_mod(n, p-1)*n) % MOD;
    ll tmp = pow_mod(n, p/2);
    return (tmp*tmp)%MOD;
}

class AlmostEulerianGraph {
public:
    int calculateGraphs(int n) {
        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] + nCr[i-1][j-1]) % MOD;
            }
        }
        for (int i = 1; i < MAXN; i++) {
            D[i] = pow_mod(2, nCr[i-1][2]);
        }
        E[1] = 1; E[2] = 0;
        for (int i = 3; i <= n; i++) {
            ll minus = 0;
            for (int k = 1; k < i; k++) {
                ll tmp = nCr[i-1][k-1] * E[k] % MOD;
                (tmp *= D[i-k]) %= MOD;
                (minus += tmp) %= MOD;
            }
            E[i] = (D[i]-minus+MOD) % MOD;
        }
        return E[n] * (n*(n-1)/2+1) % MOD;
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 672 div1 med:AlmostEulerianGraph

問題

解法

得た知見