結果
問題 |
No.3230 Mutual Corresponding System
|
ユーザー |
|
提出日時 | 2025-08-08 23:18:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 112 ms / 2,000 ms |
コード長 | 3,017 bytes |
コンパイル時間 | 1,115 ms |
コンパイル使用メモリ | 110,212 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-08-08 23:18:44 |
合計ジャッジ時間 | 3,260 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <algorithm> #include <cassert> #include <iostream> #include <vector> // #include <atcoder/all> using namespace std; // using namespace atcoder; // using mint = modint998244353; using lint = long long; const lint infty = 9223372036854775807ll; template <typename T> void chmax(T &x, const T y) { x = max(x, y); } template <typename T> struct Matrix { using Vec = vector<T>; using Arr = vector<Vec>; int h, w; Arr a; Matrix(int h, int w) : h(h), w(w), a(h, Vec(w)) {} Matrix(const Vec &v) : h(v.size()), w(1) { for (auto x : v) { a.push_back({x}); } } Matrix &unit() { assert(h == w); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { a[i][j] = i == j ? T(0) : T(-infty); // a[i][j] = T(infty); } } return *this; } Vec &operator[](int i) { return a[i]; } const Vec &operator[](int i) const { return a[i]; } Vec as_vec() const { assert(w == 1); Vec ans; for (int i = 0; i < h; i++) { ans.push_back(a[i][0]); } return ans; } Matrix operator*(const Matrix &b) const { assert(w == b.h); Matrix ans(h, b.w); for (int i = 0; i < h; i++) { for (int j = 0; j < b.w; j++) { ans[i][j] = T(-infty); for (int k = 0; k < w; k++) { // ans.a[i][k] += a[i][j] * b.a[j][k]; // ans[i][j] += a[i][k] * b[k][j]; chmax(ans[i][j], (a[i][k] + b[k][j])); } } } return ans; } void print() const { cout << "[\n"; for (auto &ai : a) { cout << " ( "; for (auto &b : ai) { // cout << b.val() << " "; cout << b << " "; } cout << ")" << endl; } cout << "]" << endl; } Matrix pow(long long n) const { assert(h == w); if (!n) return Matrix(h, h).unit(); if (n == 1) return *this; Matrix h = pow(n >> 1); h = h * h; if (n & 1) h = h * (*this); return h; // Matrix x = *this, r = Matrix(h, h).unit(); // while (n) { // if (n & 1) r = r * x; // x = x * x; // n >>= 1; // } // return r; } }; int main() { lint n, m; cin >> n >> m; vector<lint> v(n); for (auto &e : v) cin >> e; Matrix<lint> mat(n, n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> mat[j][i]; } } auto mp = mat.pow(m - 1); // mp.print(); auto ndp = (mp * v).as_vec(); for (int i = 0; i < n; ++i) mat[i][i] = -infty; auto nv = (mat * ndp).as_vec(); for (int i = 0; i < n; ++i) { cout << nv[i] << " \n"[i == n - 1]; } return 0; }