#1033370 (C++23) No.2405 Minimal Matrix Decomposition

• 問題: No.2405 Minimal Matrix Decomposition
• ユーザー: Fu_L
• 提出日時: 2024-12-26 10:23:07
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 136 ms / 2,000 ms
• コード長: 9,473 bytes
• コンパイル時間: 7,384 ms
• コンパイル使用メモリ: 284,772 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-12-26 10:23:21
• 合計ジャッジ時間: 14,196 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
sample	AC * 4
other	AC * 46

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
struct Barrett {
    explicit Barrett(const unsigned int m)
        : _m(m), im((unsigned long long)(-1) / m + 1) {}
    inline unsigned int umod() const {
        return _m;
    }
    inline unsigned int mul(const unsigned int a, const unsigned int b) const {
        unsigned long long z = a;
        z *= b;
        const unsigned long long x = (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
        unsigned int v = (unsigned int)(z - x * _m);
        if(_m <= v) v += _m;
        return v;
    }

   private:
    unsigned int _m;
    unsigned long long im;
};
template <int id>
struct DynamicModint {
    using mint = DynamicModint;
    static int mod() {
        return (int)bt.umod();
    }
    static void set_mod(const int m) {
        assert(1 <= m);
        bt = Barrett(m);
    }
    static mint raw(const int v) {
        mint a;
        a._v = v;
        return a;
    }
    DynamicModint()
        : _v(0) {}
    template <class T>
    DynamicModint(const T& v) {
        static_assert(is_integral_v<T>);
        if(is_signed_v<T>) {
            long long x = (long long)(v % (long long)(umod()));
            if(x < 0) x += umod();
            _v = (unsigned int)(x);
        } else _v = (unsigned int)(v % umod());
    }
    unsigned int val() const {
        return _v;
    }
    mint& operator++() {
        ++_v;
        if(_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if(_v == 0) _v = umod();
        --_v;
        return *this;
    }
    mint operator++(int) {
        mint res = *this;
        ++*this;
        return res;
    }
    mint operator--(int) {
        mint res = *this;
        --*this;
        return res;
    }
    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if(_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += mod() - rhs._v;
        if(_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        _v = bt.mul(_v, rhs._v);
        return *this;
    }
    mint& operator/=(const mint& rhs) {
        return *this *= rhs.inv();
    }
    mint operator+() const {
        return *this;
    }
    mint operator-() const {
        return mint() - *this;
    }
    mint pow(long long n) const {
        assert(0 <= n);
        if(n == 0) return 1;
        mint x = *this, r = 1;
        while(1) {
            if(n & 1) r *= x;
            n >>= 1;
            if(n == 0) return r;
            x *= x;
        }
    }
    mint inv() const {
        const auto eg = inv_gcd(_v, mod());
        assert(eg.first == 1);
        return eg.second;
    }
    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }
    friend istream& operator>>(istream& in, mint& x) {
        long long a;
        in >> a;
        x = a;
        return in;
    }
    friend ostream& operator<<(ostream& out, const mint& x) {
        return out << x.val();
    }

   private:
    unsigned int _v = 0;
    static Barrett bt;
    inline static unsigned int umod() {
        return bt.umod();
    }
    inline static pair<long long, long long> inv_gcd(const long long a, const long long b) {
        if(a == 0) return {b, 0};
        long long s = b, t = a, m0 = 0, m1 = 1;
        while(t) {
            const long long u = s / t;
            s -= t * u;
            m0 -= m1 * u;
            swap(s, t);
            swap(m0, m1);
        }
        if(m0 < 0) m0 += b / s;
        return {s, m0};
    }
};
template <int id>
Barrett DynamicModint<id>::bt(998244353);
using modint = DynamicModint<-1>;
using mint = modint;
template <typename T>
struct Matrix {
    Matrix(const int h, const int w, const T& val = 0)
        : h(h), w(w), A(h, vector<T>(w, val)) {}
    int H() const {
        return h;
    }
    int W() const {
        return w;
    }
    const vector<T>& operator[](const int i) const {
        assert(0 <= i and i < h);
        return A[i];
    }
    vector<T>& operator[](const int i) {
        assert(0 <= i and i < h);
        return A[i];
    }
    static Matrix I(const int n) {
        Matrix mat(n, n);
        for(int i = 0; i < n; ++i) mat[i][i] = 1;
        return mat;
    }
    Matrix& operator+=(const Matrix& B) {
        assert(h == B.h and w == B.w);
        for(int i = 0; i < h; ++i) {
            for(int j = 0; j < w; ++j) {
                (*this)[i][j] += B[i][j];
            }
        }
        return (*this);
    }
    Matrix& operator-=(const Matrix& B) {
        assert(h == B.h and w == B.w);
        for(int i = 0; i < h; ++i) {
            for(int j = 0; j < w; ++j) {
                (*this)[i][j] -= B[i][j];
            }
        }
        return (*this);
    }
    Matrix& operator*=(const Matrix& B) {
        assert(w == B.h);
        vector<vector<T>> C(h, vector<T>(B.w, 0));
        for(int i = 0; i < h; ++i) {
            for(int k = 0; k < w; ++k) {
                for(int j = 0; j < B.w; ++j) {
                    C[i][j] += (*this)[i][k] * B[k][j];
                }
            }
        }
        A.swap(C);
        return (*this);
    }
    Matrix& pow(long long t) {
        assert(h == w);
        assert(t >= 0);
        Matrix B = Matrix::I(h);
        while(t > 0) {
            if(t & 1ll) B *= (*this);
            (*this) *= (*this);
            t >>= 1ll;
        }
        A.swap(B.A);
        return (*this);
    }
    Matrix operator+(const Matrix& B) const {
        return (Matrix(*this) += B);
    }
    Matrix operator-(const Matrix& B) const {
        return (Matrix(*this) -= B);
    }
    Matrix operator*(const Matrix& B) const {
        return (Matrix(*this) *= B);
    }
    bool operator==(const Matrix& B) const {
        assert(h == B.H() and w == B.W());
        for(int i = 0; i < h; ++i) {
            for(int j = 0; j < w; ++j) {
                if(A[i][j] != B[i][j]) return false;
            }
        }
        return true;
    }
    bool operator!=(const Matrix& B) const {
        assert(h == B.H() and w == B.W());
        for(int i = 0; i < h; ++i) {
            for(int j = 0; j < w; ++j) {
                if(A[i][j] != B[i][j]) return true;
            }
        }
        return false;
    }

   private:
    int h, w;
    vector<vector<T>> A;
};
template <typename T>
pair<int, T> gauss_elimination(Matrix<T>& a, int pivot_end = -1) {
    const int h = a.H(), w = a.W();
    int rank = 0;
    assert(-1 <= pivot_end and pivot_end <= w);
    if(pivot_end == -1) pivot_end = w;
    T det = 1;
    for(int j = 0; j < pivot_end; ++j) {
        int idx = -1;
        for(int i = rank; i < h; ++i) {
            if(a[i][j] != T(0)) {
                idx = i;
                break;
            }
        }
        if(idx == -1) {
            det = 0;
            continue;
        }
        if(rank != idx) det = -det, swap(a[rank], a[idx]);
        det *= a[rank][j];
        if(a[rank][j] != T(1)) {
            const T coeff = T(1) / a[rank][j];
            for(int k = j; k < w; ++k) a[rank][k] *= coeff;
        }
        for(int i = 0; i < h; ++i) {
            if(i == rank) continue;
            if(a[i][j] != T(0)) {
                const T coeff = a[i][j] / a[rank][j];
                for(int k = j; k < w; ++k) a[i][k] -= a[rank][k] * coeff;
            }
        }
        ++rank;
    }
    return {rank, det};
}
int main(void) {
    int p, n, m;
    cin >> p >> n >> m;
    mint::set_mod(p);
    Matrix<mint> a(n, m);
    bool flag = true;
    rep(i, 0, n) {
        rep(j, 0, m) {
            cin >> a[i][j];
            if(a[i][j].val() != 0) {
                flag = false;
            }
        }
    }
    Matrix<mint> b = a;
    int r = gauss_elimination(b).first;
    if(flag) r = 1;
    if(n * m <= (n + m) * r) {
        cout << 1 << '\n';
        cout << n << ' ' << m << '\n';
        rep(i, 0, n) {
            rep(j, 0, m) {
                cout << a[i][j] << " \n"[j + 1 == m];
            }
        }
    } else {
        cout << 2 << '\n';
        cout << n << ' ' << r << '\n';
        vector<int> idx(r);
        rep(i, 0, r) {
            rep(j, 0, m) {
                if(b[i][j].val() != 0) {
                    idx[i] = j;
                    break;
                }
            }
        }
        rep(i, 0, n) {
            rep(j, 0, r) {
                cout << a[i][idx[j]] << " \n"[j + 1 == r];
            }
        }
        cout << r << ' ' << m << '\n';
        rep(i, 0, r) {
            rep(j, 0, m) {
                cout << b[i][j] << " \n"[j + 1 == m];
            }
        }
    }
}