linear_algebra_matrix/test/pfaffian.test.cpp

• View this file on GitHub
• Last update: 2025-08-10 23:51:27+09:00
• Problem: https://judge.yosupo.jp/problem/pfaffian_of_matrix

Depends on

• Pfaffian of skew-symmetric matrix （歪対称行列のパフィアン） (linear_algebra_matrix/pfaffian.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/pfaffian_of_matrix"

#include "../pfaffian.hpp"

#include <iostream>
#include <vector>

#include <atcoder/modint>

using namespace std;
using mint = atcoder::modint998244353;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector A(N * 2, vector<mint>(N * 2));
    for (auto &v : A) {
        for (auto &x : v) {
            int tmp;
            cin >> tmp;
            x = tmp;
        }
    }

    cout << Pfaffian(A).val() << '\n';
}

#line 1 "linear_algebra_matrix/test/pfaffian.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/pfaffian_of_matrix"

#line 2 "linear_algebra_matrix/pfaffian.hpp"

#include <utility>
#include <vector>

// Calculate Pfaffian of Matrix
// requirement: T is field, M is skew-symmetric
// Complexity: O(n^3)
// Implementation is based on Nachia-san's submission https://judge.yosupo.jp/submission/278787
template <class T> T Pfaffian(const std::vector<std::vector<T>> &M) {
    const int n = M.size();
    if (n % 2) return T{};

    auto mat = M;
    T res{1};

    for (int s = 0; s < n; s += 2) {
        {
            int t = s + 1;
            while (t < n and mat[s][t] == T{}) ++t;
            if (t == n) return T{};

            if (t != s + 1) {
                for (int i = s; i < n; ++i) std::swap(mat[s + 1][i], mat[t][i]);
                for (int i = s; i < n; ++i) std::swap(mat[i][s + 1], mat[i][t]);
                res = -res;
            }
        }

        res *= mat[s][s + 1];

        const T w = mat[s][s + 1].inv();

        for (int i = s + 1; i < n; ++i) mat[s][i] *= w;
        for (int i = s + 1; i < n; ++i) mat[i][s] *= w;

        // mat[s+2:, s+2:] += mat[:, s] ^ mat[s + 1, :]
        for (int i = s + 2; i < n; ++i) {
            for (int j = s + 2; j < n; ++j) {
                // mat[i][j] += mat[i][s] * mat[s + 1][j] - mat[i][s + 1] * mat[s][j];
                mat[i][j] += mat[s + 1][i] * mat[s][j] - mat[s][i] * mat[s + 1][j];
            }
        }
    }

    return res;
}
#line 4 "linear_algebra_matrix/test/pfaffian.test.cpp"

#include <iostream>
#line 7 "linear_algebra_matrix/test/pfaffian.test.cpp"

#include <atcoder/modint>

using namespace std;
using mint = atcoder::modint998244353;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector A(N * 2, vector<mint>(N * 2));
    for (auto &v : A) {
        for (auto &x : v) {
            int tmp;
            cin >> tmp;
            x = tmp;
        }
    }

    cout << Pfaffian(A).val() << '\n';
}

Back to top page