結果
問題 | No.650 行列木クエリ |
ユーザー |
![]() |
提出日時 | 2020-11-11 23:20:45 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 27,893 bytes |
コンパイル時間 | 9,162 ms |
コンパイル使用メモリ | 258,048 KB |
最終ジャッジ日時 | 2025-01-15 22:10:38 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:625:20: error: expected unqualified-id before ')' token 625 | Mat<Num, H, W>() : array<array<Num, W>, H>() { fill(0); } | ^ main.cpp:626:20: error: expected unqualified-id before 'const' 626 | Mat<Num, H, W>(const Num value) : array<array<Num, W>, H>() { fill(value); } | ^~~~~ main.cpp:626:20: error: expected ')' before 'const' 626 | Mat<Num, H, W>(const Num value) : array<array<Num, W>, H>() { fill(value); } | ~^~~~~ | ) main.cpp:627:57: error: invalid declarator before 'init' 627 | Mat<Num, H, W>(std::initializer_list<array<Num, W>> init) : array<array<Num, W>, H>() { | ^~~~ main.cpp:627:56: error: expected ')' before 'init' 627 | Mat<Num, H, W>(std::initializer_list<array<Num, W>> init) : array<array<Num, W>, H>() { | ~ ^~~~~ | ) main.cpp: In function 'void solve()': main.cpp:755:32: error: could not convert '{0, {{1, 0}, {0, 1}}}' from '<brace-enclosed initializer list>' to 'T' {aka 'std::pair<long long int, Mat<mint, 2, 2> >'} 755 | T ti = {0, {{1, 0}, {0, 1}}}; // 要素の単位元 | ^ | | | <brace-enclosed initializer list> main.cpp:756:32: error: could not convert '{0, {{1, 0}, {0, 1}}}' from '<brace-enclosed initializer list>' to 'E' {aka 'std::pair<long long int, Mat<mint, 2, 2> >'} 756 | E ei = {0, {{1, 0}, {0, 1}}}; // 作用素の単位元 | ^ | | | <brace-enclosed initializer list> main.cpp:760:48: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long lon
ソースコード
/* #region Head */// #define _GLIBCXX_DEBUG#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using ld = long double;using pll = pair<ll, ll>;template <class T> using vc = vector<T>;template <class T> using vvc = vc<vc<T>>;using vll = vc<ll>;using vvll = vvc<ll>;using vld = vc<ld>;using vvld = vvc<ld>;using vs = vc<string>;using vvs = vvc<string>;template <class T, class U> using um = unordered_map<T, U>;template <class T> using pq = priority_queue<T>;template <class T> using pqa = priority_queue<T, vc<T>, greater<T>>;template <class T> using us = unordered_set<T>;#define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i))#define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i))#define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i))#define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d))#define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d))#define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)#define ALL(x) begin(x), end(x)#define SIZE(x) ((ll)(x).size())#define PERM(c) \sort(ALL(c)); \for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))#define UNIQ(v) v.erase(unique(ALL(v)), v.end());#define CEIL(a, b) (((a) + (b)-1) / (b))#define endl '\n'#define sqrt sqrtl#define floor floorl#define log2 log2lconstexpr ll INF = 1'010'000'000'000'000'017LL;constexpr int IINF = 1'000'000'007LL;constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7// constexpr ll MOD = 998244353;constexpr ld EPS = 1e-12;constexpr ld PI = 3.14159265358979323846;template <typename T> istream &operator>>(istream &is, vc<T> &vec) { // vector 入力for (T &x : vec) is >> x;return is;}template <typename T> ostream &operator<<(ostream &os, vc<T> &vec) { // vector 出力 (for dump)os << "{";REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", ");os << "}";return os;}template <typename T> ostream &operator>>(ostream &os, vc<T> &vec) { // vector 出力 (inline)REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " ");return os;}template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &pair_var) { // pair 入力is >> pair_var.first >> pair_var.second;return is;}template <typename T, typename U> ostream &operator<<(ostream &os, pair<T, U> &pair_var) { // pair 出力os << "(" << pair_var.first << ", " << pair_var.second << ")";return os;}// map, um, set, us 出力template <class T> ostream &out_iter(ostream &os, T &map_var) {os << "{";REPI(itr, map_var) {os << *itr;auto itrcp = itr;if (++itrcp != map_var.end()) os << ", ";}return os << "}";}template <typename T, typename U> ostream &operator<<(ostream &os, map<T, U> &map_var) { return out_iter(os, map_var); }template <typename T, typename U> ostream &operator<<(ostream &os, um<T, U> &map_var) {os << "{";REPI(itr, map_var) {auto [key, value] = *itr;os << "(" << key << ", " << value << ")";auto itrcp = itr;if (++itrcp != map_var.end()) os << ", ";}os << "}";return os;}template <typename T> ostream &operator<<(ostream &os, set<T> &set_var) { return out_iter(os, set_var); }template <typename T> ostream &operator<<(ostream &os, us<T> &set_var) { return out_iter(os, set_var); }template <typename T> ostream &operator<<(ostream &os, pq<T> &pq_var) {pq<T> pq_cp(pq_var);os << "{";if (!pq_cp.empty()) {os << pq_cp.top(), pq_cp.pop();while (!pq_cp.empty()) os << ", " << pq_cp.top(), pq_cp.pop();}return os << "}";}void pprint() { cout << endl; }template <class Head, class... Tail> void pprint(Head &&head, Tail &&... tail) {cout << head;if (sizeof...(Tail) > 0) cout << ' ';pprint(move(tail)...);}// dump#define DUMPOUT cerrvoid dump_func() { DUMPOUT << endl; }template <class Head, class... Tail> void dump_func(Head &&head, Tail &&... tail) {DUMPOUT << head;if (sizeof...(Tail) > 0) DUMPOUT << ", ";dump_func(move(tail)...);}// chmax (更新「される」かもしれない値が前)template <typename T, typename U, typename Comp = less<>> bool chmax(T &xmax, const U &x, Comp comp = {}) {if (comp(xmax, x)) {xmax = x;return true;}return false;}// chmin (更新「される」かもしれない値が前)template <typename T, typename U, typename Comp = less<>> bool chmin(T &xmin, const U &x, Comp comp = {}) {if (comp(x, xmin)) {xmin = x;return true;}return false;}// ローカル用#define DEBUG_#ifdef DEBUG_#define DEB#define dump(...) \DUMPOUT << " " << string(#__VA_ARGS__) << ": " \<< "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl \<< " ", \dump_func(__VA_ARGS__)#else#define DEB if (false)#define dump(...)#endif#define VAR(type, ...) \type __VA_ARGS__; \cin >> __VA_ARGS__;template <typename T> istream &operator,(istream &is, T &rhs) { return is >> rhs; }template <typename T> ostream &operator,(ostream &os, const T &rhs) { return os << ' ' << rhs; }struct AtCoderInitialize {static constexpr int IOS_PREC = 15;static constexpr bool AUTOFLUSH = false;AtCoderInitialize() {ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cout << fixed << setprecision(IOS_PREC);if (AUTOFLUSH) cout << unitbuf;}} ATCODER_INITIALIZE;void Yn(bool p) { cout << (p ? "Yes" : "No") << endl; }void YN(bool p) { cout << (p ? "YES" : "NO") << endl; }/* #endregion */// #include <atcoder/all>// using namespace atcoder;/* #region Graph */// エッジ(本来エッジは双方向だが,ここでは単方向で管理)template <class weight_t = int, class flow_t = int> struct Edge {ll src; // エッジ始点となる頂点ll dst; // エッジ終点となる頂点weight_t weight; // 重みflow_t cap;Edge() : src(0), dst(0), weight(0) {}Edge(ll src, ll dst, weight_t weight) : src(src), dst(dst), weight(weight) {}Edge(ll src, ll dst, weight_t weight, flow_t cap) : src(src), dst(dst), weight(weight), cap(cap) {}// Edge 標準出力friend ostream &operator<<(ostream &os, Edge &edge) {os << "(" << edge.src << " -> " << edge.dst << ", " << edge.weight << ")";return os;}};// 同じ頂点を始点とするエッジ集合template <class weight_t = int, class flow_t = int> class Node : public vc<Edge<weight_t, flow_t>> {public:ll idx;Node() : vc<Edge<weight_t, flow_t>>() {}// void add(int a, int b, weight_t w, flow_t cap) { this->emplace_back(a, b, w, cap); };};// graph[i] := 頂点 i を始点とするエッジ集合template <class weight_t = int, class flow_t = int> class Graph : public vc<Node<weight_t, flow_t>> {public:Graph() : vc<Node<weight_t, flow_t>>() {}Graph(int n) : vc<Node<weight_t, flow_t>>(n) { REP(i, 0, n)(*this)[i].idx = i; }// 単方向void add_arc(int a, int b, weight_t w = 1, flow_t cap = 1) { (*this)[a].emplace_back(a, b, w, cap); }// 双方向void add_edge(int a, int b, weight_t w = 1, flow_t cap = 1) { add_arc(a, b, w, cap), add_arc(b, a, w, cap); }};// using Array = vc<Weight>;// using Matrix = vc<Array>;/* #endregion *//* #region HLD */template <class weight_t = int, class flow_t = int> struct HeavyLightDecomposition {Graph<weight_t, flow_t> &g;vc<int> sz; // sz[i] := ノード i を根とする部分木のサイズvc<int> in; // in[i] := ノード i はオイラーツアー何番目かvc<int> out; // out[i] := オイラーツアー帰りがけでノード i 到達時までに計いくつノードを走査したかvc<int> head; // head[i] := HLD 後のノード i を含む木の根ノードvc<int> rev; // rev[i] := オイラーツアーで i 番目に訪れるノード(in の逆写像)vc<int> par; // par[i] := ノード i の親(0を根としたとき)HeavyLightDecomposition(Graph<weight_t, flow_t> &g): g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {}// 部分木のサイズを調べながら dfs するvoid dfs_sz(int idx, int p) {par[idx] = p;sz[idx] = 1;// 最初のエッジが親へ向いているものなら,交換可能なら交換するif (g[idx].size() >= 2ul && g[idx][0].dst == p) {swap(g[idx][0], g[idx][1]);// swap(g[idx][0], g[idx].back());}for (Edge<weight_t, flow_t> &edge : g[idx]) {if (edge.dst == p) continue;dfs_sz(edge.dst, idx);sz[idx] += sz[edge.dst];// 部分木のサイズが大きい子ノードへのエッジが先頭になるようにするif (sz[g[idx][0].dst] < sz[edge.dst]) {// dump(g[idx][0].dst, edge.dst, sz[g[idx][0].dst], sz[edge.dst]);swap(g[idx][0], edge);}}}// dfs しながら hld を実行する.void dfs_hld(int idx, int par, int ×) {in[idx] = times++;rev[in[idx]] = idx;for (Edge<weight_t, flow_t> &edge : g[idx]) {if (edge.dst == par) continue;head[edge.dst] = (g[idx][0].dst == edge.dst ? head[idx] : edge.dst);dfs_hld(edge.dst, idx, times);}out[idx] = times;}// 構築する。void build() {dfs_sz(0, -1);int t = 0;dfs_hld(0, -1, t);}// 頂点 v から頂点 0 方向に k 個だけ遡った頂点を返す。int la(int v, int k) {while (1) {int u = head[v];if (in[v] - k >= in[u]) return rev[in[v] - k];k -= in[v] - in[u] + 1;v = par[u];}}// 頂点 u と v の最小共通祖先を返す。int lca(int u, int v) {for (;; v = par[head[v]]) {if (in[u] > in[v]) swap(u, v);if (head[u] == head[v]) return u;}}/*** 頂点 u と v を通るパスに対する取得クエリを処理する。* @param ti 単位元* @param q 列に対するクエリを返す演算. (int, int) -> T.* @param f 列とは列同士の演算結果をマージする演算. (T, T) -> T.* @param edge 頂点クエリではなく辺クエリとして処理する*/template <typename T, typename Q, typename F>T query(int u, int v, const T &ti, const Q &q, const F &f, bool edge = false) {T l = ti, r = ti;for (;; v = par[head[v]]) {if (in[u] > in[v]) swap(u, v), swap(l, r);if (head[u] == head[v]) break;l = f(q(in[head[v]], in[v] + 1), l);}return f(f(q(in[u] + edge, in[v] + 1), l), r);// return {f(q(in[u] + edge, in[v] + 1), l), r};}/*** 頂点 u と v を通るパスに対する更新クエリを処理する。O(log n).* @param q 更新クエリ.半開区間で呼び出される.(left, right) -> void.* @param edge 頂点クエリではなく辺クエリとして処理する*/template <typename Q> void update(int u, int v, const Q &q, bool edge = false) {for (;; v = par[head[v]]) {if (in[u] > in[v]) swap(u, v);if (head[u] == head[v]) break;q(in[head[v]], in[v] + 1);}q(in[u] + edge, in[v] + 1);}};/* #endregion *//* #region LazySegTree */// 遅延評価セグメント木,区間更新したいときに使うやつ// 遅延伝播セグメント木について(旧:遅延評価セグメント木について) - beet's soil// http://beet-aizu.hatenablog.com/entry/2017/12/01/225955template <typename T, typename E> // T: 要素,E: 作用素struct LazySegmentTree {using F = function<T(T, T)>; // 要素と要素をマージする関数.max とか.using G = function<T(T, E)>; // 要素に作用素を作用させる関数.加算とか.using H = function<E(E, E)>; // 作用素と作用素をマージする関数.ll n, height; // 木のノード数と高さll nn; // 外から見た要素数F f; // 区間クエリで使う演算,結合法則を満たす演算.区間最大値のクエリを投げたいなら max 演算.G g; // 要素更新で使う演算,たとえば加算など.g(更新前,加算値) の形で使う.H h; // 遅延評価をまとめる際に使う演算,たとえば加算など.T ti; // 値配列の初期値.演算 f, h に関する単位元.区間最大値なら単位元は 0. (a>0 なら max(a,0)=max(0,a)=a)E ei; // 遅延配列の初期値.演算 f, h に関する単位元.区間最大値なら単位元は 0.vc<T> dat; // 1-indexed 値配列 (index は木の根から順に 1 | 2 3 | 4 5 6 7 | 8 9 10 11 12 13 14 15 | ...)vc<E> laz; // 1-indexed 遅延配列// コンストラクタ.LazySegmentTree(F f, G g, H h, T ti, E ei) : f(f), g(g), h(h), ti(ti), ei(ei) {}// 指定要素数の遅延セグメント木を初期化するvoid init(ll n_) {nn = n_;n = 1;height = 0;while (n < n_) n <<= 1, height++;dat.assign(2 * n, ti);laz.assign(2 * n, ei);}// ベクトルから遅延セグメント木を構築するvoid build(const vc<T> &v) {ll n_ = SIZE(v);init(n_);REP(i, 0, n_) dat[n + i] = v[i];REPR(i, n - 1, 1) dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]);}// 木のノード k のみに遅延評価を反映するinline T reflect(ll k) { return laz[k] == ei ? dat[k] : g(dat[k], laz[k]); }// 木のノード k について遅延伝搬処理を行う.// これにより dat[k] は更新を反映した状態になる.inline void propagate(ll k) {if (laz[k] == ei) return;// 直接の子ノードに遅延配列内容を伝搬laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k]); // 子,左側laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k]); // 子,右側dat[k] = reflect(k);laz[k] = ei;}// 木のノード k に関して,親から順に伝搬処理を行う// これにより dat[k] とその全ての親ノード dat[k>>1], dat[k>>2], ..., dat[1] が更新される.// 更新は根 dat[1] 側から順に行う.inline void thrust(ll k) { REPR(i, height, 1) propagate(k >> i); }// 木のノード k に関して,子から順に値配列の再計算を行うinline void recalc(ll k) {while (k >>= 1) dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1));}// 半開区間 [a, b) を更新するvoid update(ll a, ll b, E x) {if (a >= b) return;// assert(a < b)thrust(a += n); // インデックス a の更新thrust(b += n - 1); // インデックス b-1 の更新// 以降では l, r は木のノードfor (ll l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {if (l & 1) laz[l] = h(laz[l], x), l++; // 木のノード l が,親から見て右側の子である場合if (r & 1) --r, laz[r] = h(laz[r], x); // 木のノード r が,親から見て右側の子である場合}recalc(a);recalc(b);}// インデックス a の要素の値を x にする.void set_val(ll a, T x) {thrust(a += n);dat[a] = x;laz[a] = ei;recalc(a);}// 半開区間 [a, b) に対するクエリを実行するT query(ll a, ll b) {if (a >= b) return ti;// assert(a<b)thrust(a += n); // インデックス a の更新thrust(b += n - 1); // インデックス b-1 の更新T vl = ti, vr = ti;for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {if (l & 1) vl = f(vl, reflect(l++));if (r & 1) vr = f(reflect(--r), vr);}return f(vl, vr);}template <typename C> ll find(ll st, C &check, T &acc, ll k, ll l, ll r) {if (l + 1 == r) {acc = f(acc, reflect(k));return check(acc) ? k - n : -1;}propagate(k);ll m = (l + r) >> 1;if (m <= st) return find(st, check, acc, (k << 1) | 1, m, r);if (st <= l && !check(f(acc, dat[k]))) {acc = f(acc, dat[k]);return -1;}ll vl = find(st, check, acc, (k << 1) | 0, l, m);if (~vl) return vl;return find(st, check, acc, (k << 1) | 1, m, r);}// check が真となる要素を探して,そのインデックスを返す.template <typename C> ll find(ll st, C &check) {T acc = ti;return find(st, check, acc, 1, 0, n);}// セグメント木上の二分探索.// @param l 区間左端// @param check 条件// @return check(query(l,r)) が真となる最大の r(半開区間であることに注意).int max_right(int l, const function<bool(T)> &check) {assert(0 <= l && l <= nn);assert(check(ti));if (l == nn) return nn;l += n;for (int i = height; i >= 1; i--) propagate(l >> i);T sm = ti;do {while (l % 2 == 0) l >>= 1;if (!check(f(sm, dat[l]))) {while (l < n) {propagate(l);l = (2 * l);if (check(f(sm, dat[l]))) {sm = f(sm, dat[l]);l++;}}return l - n;}sm = f(sm, dat[l]);l++;} while ((l & -l) != l);return nn;}// セグメント木上の二分探索.// @param r 区間右端(半開区間であることに注意)// @param check 条件// @return check(query(l,r)) が真となる最小の l(半開区間であることに注意).int min_left(int r, const function<bool(T)> &check) {assert(0 <= r && r <= nn);assert(check(ti));if (r == 0) return 0;r += n;for (int i = height; i >= 1; i--) propagate((r - 1) >> i);T sm = ti;do {r--;while (r > 1 && (r % 2)) r >>= 1;if (!check(f(dat[r], sm))) {while (r < n) {propagate(r);r = (2 * r + 1);if (check(f(dat[r], sm))) {sm = f(dat[r], sm);r--;}}return r + 1 - n;}sm = f(dat[r], sm);} while ((r & -r) != r);return 0;}// セグ木の中身を標準出力する.void _dump() {REP(k, 0, nn) {T val = query(k, k + 1);cout << val << (k == nn - 1 ? '\n' : ' ');}}};/* #endregion *//* #region mint */// 自動で MOD を取る整数struct mint {ll x;mint(ll x = 0) : x((x % MOD + MOD) % MOD) {}mint &operator+=(const mint a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}mint &operator-=(const mint a) {if ((x += MOD - a.x) >= MOD) x -= MOD;return *this;}mint &operator*=(const mint a) {(x *= a.x) %= MOD;return *this;}mint operator+(const mint a) const {mint res(*this);return res += a;}mint operator-(const mint a) const {mint res(*this);return res -= a;}mint operator*(const mint a) const {mint res(*this);return res *= a;}// O(log(t))mint pow_rec(ll t) const {if (!t) return 1;mint a = pow(t >> 1); // ⌊t/2⌋ 乗a *= a; // ⌊t/2⌋*2 乗if (t & 1) // ⌊t/2⌋*2 == t-1 のときa *= *this; // ⌊t/2⌋*2+1 乗 => t 乗return a;}mint pow(ll t) const {mint a(*this);mint res = 1;while (t) {if (t & 1) res *= a;t >>= 1, a *= a;}return res;}// for prime modmint inv_prime() const {return pow(MOD - 2); // オイラーの定理から, x^(-1) ≡ x^(p-2)}mint inv() const {ll a = this->x, b = MOD, u = 1, v = 0, t;mint res;while (b) {t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}if (u < 0) u += MOD;res = u;return res;}mint &operator/=(const mint a) { return (*this) *= a.inv(); }mint operator/(const mint a) const {mint res(*this);return res /= a;}bool operator==(const mint a) const { return this->x == a.x; }bool operator==(const ll a) const { return this->x == a; }// mint 入力friend istream &operator>>(istream &is, mint &x) {is >> x.x;return is;}// mint 出力friend ostream &operator<<(ostream &os, mint x) {os << x.x;return os;}};/* #endregion *//* #region Mat */// 行列,==, !=, [] あたりは array と一緒template <class Num, size_t H, size_t W> class Mat : public array<array<Num, W>, H> {public:Mat<Num, H, W>() : array<array<Num, W>, H>() { fill(0); }Mat<Num, H, W>(const Num value) : array<array<Num, W>, H>() { fill(value); }Mat<Num, H, W>(std::initializer_list<array<Num, W>> init) : array<array<Num, W>, H>() {int i = 0;for (auto iter = init.begin(); iter != init.end(); ++iter) (*this)[i++] = array<Num, W>(*iter);}// 行列に別の行列を足すMat<Num, H, W> &operator+=(const Mat<Num, H, W> &another) {REP(i, 0, H) REP(j, 0, W)(*this)[i][j] += another[i][j];return *this;}// 行列から別の行列を引くMat<Num, H, W> &operator-=(const Mat<Num, H, W> &another) {REP(i, 0, H) REP(j, 0, W)(*this)[i][j] -= another[i][j];return *this;}// 行列に別の行列を右から掛ける// template <size_t AW> Mat<Num, H, AW> &operator*=(const Mat<Num, W, AW> &another) {// Mat<Num, H, AW> ret = {};// REP(i, 0, H) REP(j, 0, AW) REP(k, 0, W) ret[i][j] += (*this)[i][k] * another[k][j];// *this = ret;// return *this;// }// 更新する場合,行列サイズが変わらない乗算のみ許容するMat<Num, H, W> &operator*=(const Mat<Num, W, W> &another) {Mat<Num, H, W> ret = (*this) * another;*this = ret;return *this;}// 行列に別の行列を足すMat<Num, H, W> operator+(const Mat<Num, H, W> &another) const {Mat<Num, H, W> ret(*this);return ret += another;}// 行列から別の行列を引くMat<Num, H, W> operator-(const Mat<Num, H, W> &another) const {Mat<Num, H, W> ret(*this);return ret -= another;}// 行列に別の行列を右から掛けるtemplate <size_t AW> Mat<Num, H, AW> operator*(const Mat<Num, W, AW> &another) const {// Mat<Num, H, AW> ret(*this);// return ret *= another;Mat<Num, H, AW> ret = {};REP(i, 0, H) REP(j, 0, AW) REP(k, 0, W) ret[i][j] += (*this)[i][k] * another[k][j];return ret;}// 行列の n 乗を計算するMat<Num, H, W> pow(ll n) const {assert(H == W);Mat<Num, H, W> ret = {};Mat<Num, H, W> a(*this);REP(i, 0, H) ret[i][i] = 1;while (n) {if (n & 1) ret = a * ret;a = a * a, n >>= 1;}return ret;}// 列和が 1 になるよう正規化するMat<Num, H, W> norm() const {array<Num, W> s = {};Mat<Num, H, W> a(*this);REP(i, 0, H) REP(j, 0, W) s[j] += a[i][j];REP(i, 0, H) REP(j, 0, W) a[i][j] /= s[j];return a;}// 行列の n 乗を計算する(列和が常に 1 になるよう正規化する)Mat<Num, H, W> pow_norm(ll n) const {assert(H == W);Mat<Num, H, W> ret = {};Mat<Num, H, W> a(*this);REP(i, 0, H) ret[i][i] = 1;while (n) {if (n & 1) ret = (a * ret).norm();a = (a * a).norm(), n >>= 1;}return ret;}template <class... T> Mat<Num, H, W> assign(T... nums) {vc<Num> num_list = vc<Num>{nums...};assert(SIZE(num_list) == H * W);REP(i, 0, H) REP(j, 0, W)(*this)[i][j] = num_list[W * i + j];return *this;}void fill(Num num) { REP(i, 0, H) REP(j, 0, W)(*this)[i][j] = num; }void print() { REP(i, 0, H) REP(j, 0, W) cout << (*this)[i][j] << (j == W - 1 ? '\n' : ' '); }void dump_col(ll j) { REP(i, 0, H) cout << (*this)[i][j] << (i == H - 1 ? '\n' : ' '); }};/* #endregion */// Problemvoid solve() {using mat = Mat<mint, 2, 2>;VAR(ll, n);vll a(n - 1), b(n - 1);REP(i, 0, n - 1) cin >> a[i] >> b[i];Graph<> graph(n);REP(i, 0, n - 1) graph.add_edge(a[i], b[i]);HeavyLightDecomposition<> hld(graph);hld.build();// segtreeusing T = pair<ll, mat>; // 要素 (要素数, 値)using E = pair<ll, mat>; // 作用素 (世代,値)auto f = [](T a, T b) -> T { // 要素のマージreturn {a.first + b.first, a.second * b.second};};auto g = [](T a, E b) -> T { // 作用素適用return {a.first, b.second.pow(a.first)};};auto h = [](E a, E b) -> E {if (a.first > b.first) return a;return b;};T ti = {0, {{1, 0}, {0, 1}}}; // 要素の単位元E ei = {0, {{1, 0}, {0, 1}}}; // 作用素の単位元LazySegmentTree<T, E> seg(f, g, h, ti, ei);// seg.init(n); // ti で初期化vc<T> data(n);REP(i, 0, n) data[i] = {1, {{1, 0}, {0, 1}}};seg.build(data);ll gen = 0;auto query = [&](int a, int b) -> T { return seg.query(a, b); };VAR(ll, q);REP(k, 0, q) {VAR(char, xg);if (xg == 'x') {VAR(ll, i);VAR(mint, x00, x01, x10, x11);mat val = {{x00, x01}, {x10, x11}};gen++;auto update = [&](int a, int b) -> void { seg.update(a, b, {gen, val}); };hld.update(a[i], b[i], update, true);} else {VAR(ll, i, j);T result = hld.query(i, j, ti, query, f, true);// dump(result.first);mat m = result.second;pprint(m[0][0], m[0][1], m[1][0], m[1][1]);}}}// entry pointint main() {solve();return 0;}