2020-10-31

AtCoder ARC 107 C - Shuffle Permutation (水色, 500 点)

面白かった

問題へのリンク

問題概要

$N \times N$ の行列 $a$ と、整数 $K$ が与えられる。この行列は、 $1,2, \dots ,N^{2}$ をちょうど一つずつ要素に含む。

sigma くんは、以下の 2 種類の操作を、好きな順序で好きな回数行えます。

全ての $i$ について $a_{i,x} +a_{i, y} \le K$ を満たす $x, y$ を選び、行列の $x, y$ 列目をswapする
全ての $i$ について $a_{x,i} + a_{y,i} \le K$ を満たす $x, y$ を選び、行列の $x, y$ 行目をswapする。

最終的に得られる行列は何種類存在するでしょうか？ mod998244353 で答えてください。

制約

$1 \le N \le 50$

考えたこと

$N$ が小さいので、ある程度雑なことができそう！！！
とりあえず、行と列を完全に独立に考えて良いことはすぐにわかった。たとえ列をどのように swap しても、 $i$ 行目と $j$ 行目を swap できるかどうかの状況は変化しない。

というわけで、行について考えることした。

行の swap

まずは、任意の $(i, j)$ に対して、 $i$ 行目と $j$ 行目が swap できるかどうかを判定していく。この作業に $O(N^{3})$ かかる。

そして、 $i$ 行目と $j$ 行目とが swap できるとき、UnionFind 上で $i, j$ が同じグループであると扱うことにする。

このとき、UnionFind 上で形成されるグループ $a_{1}, \dots, a_{m}$ について考えると、これらの順列をすべて実現することができる！！！

念のために帰納法で示すことができる。同じグループ内のノードであれば、互いに swap できるノード同士に辺を張ったとき連結になるはずである。よってその全域木をとることができる。その全域木の葉を 1 つ選んで、その値をグループ内の任意の値に変えることができる。あとは帰納法の仮定から、任意の順列が実現できる！！！

よって、UnionFind 上の各グループのサイズを $m_{1}, \dots$ として、 $m_{1}!$ を掛けていけば OK。

コード

計算量は $O(N^{3})$ となる。

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

// modint
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() const { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept {
        if (n == 0) return 1;
        if (n < 0) return modpow(modinv(r), -n);
        auto t = modpow(r, n / 2);
        t = t * t;
        if (n & 1) t = t * r;
        return t;
    }
    friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Fp<MOD>(u);
    }
};


const int MOD = 998244353;
using mint = Fp<MOD>;

template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

BiCoef<mint> bc;



mint solve(int N, long long K, const vector<vector<long long>> &a) {
    UnionFind uf(N);
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j < N; ++j) {
            bool ok = true;
            for (int k = 0; k < N; ++k) {
                if (a[i][k] + a[j][k] > K) ok = false;
            }
            if (ok) uf.merge(i, j);
        }
    }
    mint res = 1;
    for (int i = 0; i < N; ++i) {
        if (uf.root(i) == i) res *= bc.fact(uf.size(i));
    }
    return res;
}

int main() {
    bc.init(1000);
    int N;
    long long K;
    cin >> N >> K;
    vector<vector<long long>> a(N, vector<long long>(N));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> a[i][j];

    mint res1 = solve(N, K, a);
    for (int i = 0; i < N; ++i) for (int j = i+1; j < N; ++j) swap(a[i][j], a[j][i]);
    mint res2 = solve(N, K, a);
    cout << res1 * res2 << endl;
}