結果
問題 |
No.3227 Matrix Query
|
ユーザー |
|
提出日時 | 2025-08-08 22:14:33 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 644 ms / 8,000 ms |
コード長 | 3,473 bytes |
コンパイル時間 | 3,408 ms |
コンパイル使用メモリ | 181,456 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-08 22:15:26 |
合計ジャッジ時間 | 16,098 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <algorithm> #include <array> #include <iostream> #include <vector> #include <atcoder/all> // using namespace std; // using namespace atcoder; // using mint = modint998244353; template <typename T> struct mat22 { using mat_t = std::array<T, 4>; mat_t a; mat22() : a{} {} mat22(const mat_t &a_) : a(a_) {} // mat22(const Vec &v) : h(v.size()), w(1) // { // for (auto x : v) { // a.push_back({x}); // } // } static mat22<T> unit() { mat22<T> u; u[0] = 1; u[3] = 1; return u; } T &operator[](int i) { return a[i]; } const T &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; // } mat22<T> operator*(const mat22<T> &b) const { mat22<T> ans{}; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { // ans.a[i][k] += a[i][j] * b.a[j][k]; ans[i * 2 + j] += a[i * 2 + k] * b[k * 2 + j]; } } } return ans; } // void print() const // { // cout << "[\n"; // for (auto &ai : a) { // cout << " ( "; // for (auto &b : ai) { // cout << b.val() << " "; // } // cout << ")" << endl; // } // cout << "]" << endl; // } mat22<T> pow(long long n) const { if (!n) return mat22<T>::unit(); if (n == 1) return *this; mat22 h = pow(n >> 1); h = h * h; if (n & 1) h = h * (*this); return h; // mat22 x = *this, r = mat22(h, h).unit(); // while (n) { // if (n & 1) r = r * x; // x = x * x; // n >>= 1; // } // return r; } static mat22<T> read() { mat22<T> m; for (auto &e : m.a) { long long x; std::cin >> x; e = x; } return m; } }; template <typename Mint> struct Binomial { std::vector<Mint> fact, invfact; Binomial(int nn) : fact(nn, 1), invfact(nn, 1) { for (int i = 0; i < nn - 1; i++) fact[i + 1] = fact[i] * (i + 1); invfact[nn - 1] = fact[nn - 1].inv(); for (int i = nn - 2; i >= 0; i--) invfact[i] = invfact[i + 1] * (i + 1); } Mint operator()(int x, int y) const { if (x < 0 || y < 0 || x - y < 0) return 0; return fact[x] * invfact[y] * invfact[x - y]; } }; using mint = atcoder::modint; mat22<mint> e() { return mat22<mint>::unit(); } mat22<mint> op(mat22<mint> a, mat22<mint> b) { return a * b; } int main() { using namespace std; using lint = long long; lint k, n; cin >> k >> n; mint::set_mod(k); vector<mat22<mint>> a0(n); for (auto& ai: a0) { ai = mat22<mint>::read(); } atcoder::segtree<mat22<mint>, op, e> seg(a0); int q; cin >> q; while (q --> 0) { int i, l, r; cin >> i >> l >> r; auto y = mat22<mint>::read(); i--; l--; seg.set(i, y); auto z = seg.prod(l, r); cout << z[0].val() << " " << z[1].val() << "\n"; cout << z[2].val() << " " << z[3].val() << "\n"; } }