読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 054 C - 鯛焼き

AtCoder

ほとんどの人にとって知識ゲー or ググりゲーだったんですが, 日本語でしかググらなかったのはミスでした。

解法

結論から言いますと, 行列 S の行列式の偶奇を見れば終わりです。

理由を考えていきます。

この問題では要するにタイヤと木の完全マッチングの場合の数の偶奇を求めるわけですが, これは次の条件を満たす順列 P の数と同じです。

  • i - P[i] のペアについて, S[i][P[i]] = 1 となっている

このような順列の数は,

 \sum_P^{} \prod_{i=0}^N S_{i, P_i}

で表すことができます。(後半の  \Pi の部分で, S[i][P[i]] がすべて 1 なら完全マッチングの個数が 1 加えられることになるが, すべて 1 になることは完全マッチングを表しているので OK)

一方で, 行列の行列式の定義は,

 \sum_P^{} sgn(P) \prod_{i=0}^N S_{i, P_i}

です(P の部分はよく  \sigma を使うけどまぁ同じです)。sgn(P) は順列 P の並び方によって +1 になったり -1 になったりしますが, 今回そこは重要ではないです。

どちらにしても,  \Pi の部分が 1 になっていると, mod 2 の世界では +1 されたのと同じです。よって, 偶奇を調べる上では行列式の偶奇と完全マッチングの個数は一致してるわけですね。

typedef long long number;
typedef vector<number> vec;
typedef vector<vec> matrix;

ll mod_pow(ll x, ll p, ll MOD) {
    ll a = 1;
    while (p) {
        if (p%2) a = a*x%MOD;
        x = x*x%MOD;
        p/=2;
    }
    return a;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    return mod_pow(a, m-2, m);
}

// long long 専用 行列式を求める関数
number det(matrix A, const ll MOD) {
    const int n = A.size();
    assert(n == (int)A[0].size());
    ll ans = 1;
    for (int i = 0; i < n; i++) {
        int pivot = -1;
        for (int j = i; j < n; j++) if (A[j][i]) {
            pivot = j;
            break;
        }
        if (pivot == -1) return 0;
        if (i!=pivot) {
            swap(A[i], A[pivot]);
            ans *= -1;
        }
        ll inv = mod_inverse(A[i][i], MOD);
        for (int j = i+1; j < n; j++) {
            ll c = A[j][i]*inv % MOD;
            for (int k = i; k < n; k++) {
                A[j][k] = (A[j][k] - c*A[i][k])%MOD;
            }
        }
        (ans *= A[i][i]) %= MOD;
    }
    if (ans < 0) ans += MOD;
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    matrix S(N, vec(N));
    for (int i = 0; i < N; i++) {
    	string s;
    	cin >> s;
    	for (int j = 0; j < N; j++)
    		S[i][j] = s[j]-'0';
    }
    if (det(S, 2)) cout << "Odd" << endl;
    else cout << "Even" << endl;
    return 0;
}