結果

問題 No.2825 Sum of Scores of Sets of Specified Sections
コンテスト
ユーザー みどりむし🦠
提出日時 2024-01-21 23:21:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,732 bytes
コンパイル時間 1,591 ms
コンパイル使用メモリ 115,764 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-26 19:59:50
合計ジャッジ時間 3,879 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cassert>
#include <vector>
#include <ranges>
#include <atcoder/modint>

using mint = atcoder::modint998244353;

std::istream& operator>>(std::istream& is, mint& v) {
  int r; is >> r;
  v = r;
  return is;
}

std::ostream& operator<<(std::ostream& os, const mint& v) {
  return os << v.val();
}

template<class T>
struct matrix {
  int height, width;
  std::vector<std::vector<T>> data;

  matrix(int n, int m) : height(n), width(m), data(n, std::vector<T>(m)) {}
  
  static matrix identity(int n) {
    matrix res(n, n);
    for(int i : std::views::iota(0, n)) res[i][i] = 1;
    return res;
  } 

  inline const std::vector<T>& operator[](const int p) const {
    return this->data[p];
  }

  inline std::vector<T>& operator[](const int p) {
    return this->data[p];
  }

  friend std::istream& operator>>(std::istream& is, matrix& p) {
    for(auto& row : p.data) for(auto& v : row) is >> v;
    return is;
  }

  matrix &operator+=(const matrix &other) {
    const int n = this->height, m = this->width;
    assert(n == other.height && m == other.width);
    for(int i : std::views::iota(0, n)) {
      for(int j : std::views::iota(0, m)) {
        (*this)[i][j] += other[i][j];
      }
    }
    return *this;
  }

  matrix &operator*=(const matrix &other) {
    const int n = this->height, m = other.width, l = this->width;
    assert(l == other.height);
    matrix product(n, m);
    for(int i : std::views::iota(0, n)) {
      for(int j : std::views::iota(0, m)) {
        for(int k : std::views::iota(0, l)) {
          product[i][j] += (*this)[i][k] * other[k][j];
        }
      }
    }
    this->height = n, this->width = m;
    this->data = std::move(product.data);
    return *this;
  }

  T det() {
    auto X = this->data;
    T res = 1;
    for(int i : std::views::iota(0, this->width)) {
      int idx = -1;
      for(int j : std::views::iota(i, this->width)) {
        if(X[j][i] != 0) idx = j;
      }
      if(idx == -1) return 0;
      if(i != idx) {
        res *= -1;
        std::swap(X[i], X[idx]);
      }
      res *= X[i][i];
      const T v = X[i][i];
      for(int j : std::views::iota(0, this->width)) {
        X[i][j] /= v;
      }
      for(int j = i + 1; j < this->width; j++) {
        const T u = X[j][i];
        for(int k = 0; k < this->width; k++) {
          X[j][k] -= X[i][k] * u;
        }
      }
    }
    return res;
  }
  
  friend matrix operator+(matrix a, const matrix& b) { return a += b; }
  friend matrix operator*(matrix a, const matrix& b) { return a *= b; }
};

int main() {
  int n, m; std::cin >> n >> m;
  matrix<mint> A(n, m), B(m, n);
  std::cin >> A >> B;
  std::cout << (matrix<mint>::identity(n) + A * B).det() << "\n";
  return 0;
}
0