#626258 (C++17) No.1421 国勢調査 (Hard)

提出ソース

結果

問題	No.1421 国勢調査 (Hard)
ユーザー	m_tsubasa
提出日時	2021-03-06 02:22:44
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,898 ms / 2,000 ms
コード長	8,518 bytes
コンパイル時間	2,583 ms
コンパイル使用メモリ	207,268 KB
実行使用メモリ	10,584 KB
最終ジャッジ日時	2024-04-16 17:46:32
合計ジャッジ時間	14,139 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	4 ms 5,376 KB
testcase_03	AC	3 ms 5,376 KB
testcase_04	AC	3 ms 5,376 KB
testcase_05	AC	4 ms 5,376 KB
testcase_06	AC	4 ms 5,376 KB
testcase_07	AC	3 ms 5,376 KB
testcase_08	AC	3 ms 5,376 KB
testcase_09	AC	4 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	4 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	3 ms 5,376 KB
testcase_17	AC	3 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	3 ms 5,376 KB
testcase_22	AC	1,884 ms 10,584 KB
testcase_23	AC	1,878 ms 10,456 KB
testcase_24	AC	1,887 ms 10,456 KB
testcase_25	AC	1,898 ms 10,368 KB
testcase_26	AC	1,878 ms 10,452 KB
testcase_27	AC	87 ms 10,496 KB
testcase_28	AC	178 ms 10,448 KB
testcase_29	AC	119 ms 10,496 KB
testcase_30	AC	87 ms 10,496 KB
testcase_31	AC	117 ms 10,496 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

template <int mod = (int)(2)>
struct ModInt {
  int x;
  constexpr ModInt() : x(0) {}
  constexpr ModInt(int64_t y)
      : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  constexpr ModInt &operator+=(const ModInt &p) noexcept {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt &p) noexcept {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt &p) noexcept {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  constexpr ModInt &operator/=(const ModInt &p) noexcept {
    *this *= p.inverse();
    return *this;
  }
  constexpr ModInt operator-() const { return ModInt(-x); }
  constexpr ModInt operator+(const ModInt &p) const noexcept {
    return ModInt(*this) += p;
  }
  constexpr ModInt operator-(const ModInt &p) const noexcept {
    return ModInt(*this) -= p;
  }
  constexpr ModInt operator*(const ModInt &p) const noexcept {
    return ModInt(*this) *= p;
  }
  constexpr ModInt operator/(const ModInt &p) const noexcept {
    return ModInt(*this) /= p;
  }
  constexpr bool operator==(const ModInt &p) const noexcept { return x == p.x; }
  constexpr bool operator!=(const ModInt &p) const noexcept { return x != p.x; }
  constexpr ModInt inverse() const noexcept {
    int a = x, b = mod, u = 1, v = 0, t = 0;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  constexpr ModInt pow(int64_t n) const {
    ModInt res(1), mul(x);
    while (n) {
      if (n & 1) res *= mul;
      mul *= mul;
      n >>= 1;
    }
    return res;
  }
  friend constexpr ostream &operator<<(ostream &os, const ModInt &p) noexcept {
    return os << p.x;
  }
  friend constexpr istream &operator>>(istream &is, ModInt &a) noexcept {
    int64_t t = 0;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }
  constexpr int get_mod() { return mod; }
};
using mint = ModInt<>;

template <class T>
struct Matrix {
  vector<vector<T>> A;
  Matrix() {}
  Matrix(size_t m, size_t n) : A(m, vector<T>(n, 0)) {}
  Matrix(size_t n) : A(n, vector<T>(n, 0)) {}
  size_t height() const { return (A.size()); }
  size_t width() const { return (A[0].size()); }
  inline const vector<T> &operator[](int k) const { return (A.at(k)); }
  inline vector<T> &operator[](int k) { return (A.at(k)); }
  static Matrix E(size_t n) {
    Matrix mat(n);
    for (int i = 0; i < n; ++i) mat[i][i] = 1;
    return (mat);
  }
  Matrix &operator+=(const Matrix &B) {
    size_t m = height(), n = width();
    assert(m == B.height() && n == B.width());
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) (*this)[i][j] += B[i][j];
    return (*this);
  }
  Matrix &operator-=(const Matrix &B) {
    size_t m = height(), n = width();
    assert(m == B.height() && n == B.width());
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) (*this)[i][j] -= B[i][j];
    return (*this);
  }
  Matrix &operator*=(const Matrix &B) {
    size_t m = height(), n = B.width(), p = width();
    assert(p == B.height());
    vector<vector<T>> C(m, vector<T>(n, 0));
    for (int i = 0; i < m; ++i)
      for (int k = 0; k < p; ++k) {
        T tmp = (*this)[i][k];
        for (int j = 0; j < n; ++j) C[i][j] += tmp * B[k][j];
      }
    A.swap(C);
    return (*this);
  }
  Matrix &operator^=(long long k) {
    Matrix B = Matrix::E(height());
    while (k) {
      if (k & 1) B *= *this;
      *this *= *this;
      k >>= 1;
    }
    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); }
  Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); }

  Matrix trans() {
    size_t m = height(), n = width();
    Matrix res(n, m);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j) res[i][j] = (*this)[j][i];
    return res;
  }

  Matrix inv() {
    assert(height() == width());
    size_t n = height();
    Matrix B(n, 2 * n);
    for (int i = 0; i < n; ++i) {
      B[i][i + n] = 1;
      for (int j = 0; j < n; ++j) B[i][j] = (*this)[i][j];
    }
    for (int i = 0; i < n; ++i) {
      int piv = i;
      for (int j = i; j < n; ++j)
        if (abs(B[j][i]) > abs(B[piv][i])) piv = j;
      // not exist or unique
      assert(abs(B[piv][i]) >= 0);
      swap(B[i], B[piv]);
      for (int j = i + 1; j < 2 * n; ++j) B[i][j] /= B[i][i];
      for (int j = 0; j < n; ++j)
        if (i != j)
          for (int k = i + 1; k < 2 * n; ++k) B[j][k] -= B[j][i] * B[i][k];
    }
    Matrix res(n);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) res[i][j] = B[i][j + n];
    return res;
  }

  T det() {
    int m = height(), n = width();
    assert(m == n);
    T res = 1;
    Matrix B(m);
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) B[i][j] = (*this)[i][j];
    for (int i = 0; i < n; ++i) {
      int piv = i;
      for (int j = i + 1; j < m; ++j)
        if (B[j][i] != 0) {
          piv = j;
          break;
        }
      // if (abs(B[j][i]) > abs(B[piv][i])) piv = j;
      if (B[piv][i] == 0) return (T)0;
      // if (abs(B[piv][i]) < EPS) return (T)0;  // B[piv][i] < EPS
      if (piv != i) swap(B[i], B[piv]), res = -res;
      res *= B[i][i];
      // for (int j = i + 1; j < m; ++j)
      //   for (int k = n - 1; k >= i; --k) B[j][k] -= B[i][k] * B[j][i] /
      //   B[i][i];
      {
        const T d = (T)1 / B[i][i];
        for (int j = i + 1; j < n; ++j) B[i][j] *= d;
        for (int j = i + 1; j < m; ++j)
          for (int k = i + 1; k < n; ++k) B[j][k] -= B[i][k] * B[j][i];
      }
    }
    return res;
  }

  friend ostream &operator<<(ostream &os, Matrix &p) {
    size_t m = p.height(), n = p.width();
    for (int i = 0; i < m; i++) {
      os << "[";
      for (int j = 0; j < n; j++) {
        os << p[i][j] << (j + 1 == n ? "]\n" : ",");
      }
    }
    return (os);
  }
};

// use Matrix, ModInt
// MOD ver.
#define MOD (long long)(2)
int gauss_jordan(Matrix<ModInt<MOD>> &A, bool is_extended = false) {
  int m = A.height(), n = A.width(), rank = 0;
  using P = pair<int, int>;
  for (int col = 0; col < n; ++col) {
    if (is_extended && col == n - 1) break;
    int piv = -1;
    for (int row = rank; row < m; ++row)
      if (A[row][col] != 0) {
        piv = row;
        break;
      }
    if (piv == -1) continue;
    swap(A[piv], A[rank]);
    ModInt<MOD> inv = A[rank][col].inverse();
    for (int col2 = 0; col2 < n; ++col2) A[rank][col2] *= inv;
    for (int row = 0; row < m; ++row)
      if (row != rank && A[row][col] != 0) {
        ModInt<MOD> fac = A[row][col];
        for (int col2 = 0; col2 < n; ++col2)
          A[row][col2] -= A[rank][col2] * fac;
      }
    ++rank;
  }
  return rank;
}

int linear_equation(Matrix<ModInt<MOD>> A, vector<ModInt<MOD>> b,
                    vector<ModInt<MOD>> &ans) {
  int m = A.height(), n = A.width();
  Matrix<ModInt<MOD>> M(m, n + 1);
  assert((int)b.size() == m);
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) M[i][j] = A[i][j];
    M[i][n] = b[i];
  }
  int rank = gauss_jordan(M, 1);
  ans.assign(n, 0);
  for (int i = 0; i < rank; ++i) {
    int id = -1;
    for (int j = 0; j < n; ++j)
      if (M[i][j] != 0) {
        id = j;
        break;
      }
    ans[id] = M[i][n];
  }
  // exist?
  for (int row = rank; row < m; ++row)
    if (M[row][n] != 0) return -1;
  return rank;
}

int n, m;
vector<long long> city, bits;

vector<long long> solve();

int main() {
  cin >> n >> m;
  city.assign(m, 0);
  bits.assign(m, 0);
  for (int i = 0; i < m; ++i) {
    int len;
    cin >> len;
    while (len--) {
      int p;
      cin >> p;
      city[i] |= 1LL << --p;
    }
    cin >> bits[i];
  }

  auto res = solve();
  if (res.size())
    for (auto p : res) cout << p << endl;
  else
    cout << -1 << endl;
  return 0;
}

vector<long long> solve() {
  vector<long long> res(n, 0);
  Matrix<ModInt<MOD>> A(m, n);
  for (int i = 0; i < m; ++i)
    for (int j = 0; j < n; ++j) A[i][j] = city[i] >> j & 1;
  for (int i = 0; i < 60; ++i) {
    vector<ModInt<MOD>> b(m), ans(n);
    for (int j = 0; j < m; ++j) b[j] = bits[j] >> i & 1;
    if (linear_equation(A, b, ans) < 0) return vector<long long>();
    for (int j = 0; j < n; ++j)
      if (ans[j] == 1) res[j] |= 1LL << i;
  }
  return res;
}

yukicoder

結果

テストケース

ソースコード