結果
問題 | No.650 行列木クエリ |
ユーザー |
![]() |
提出日時 | 2021-01-19 07:59:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,337 ms / 2,000 ms |
コード長 | 18,978 bytes |
コンパイル時間 | 4,418 ms |
コンパイル使用メモリ | 375,120 KB |
最終ジャッジ日時 | 2025-01-18 02:31:07 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
//#pragma warning(disable:4996)//#include <Windows.h>#include <iostream>#include <vector>#include <limits.h>#include <algorithm>#include <string>#include <math.h>#include <limits.h>#include <queue>#include <map>#include <set>#include <iomanip>#include <bitset>#include <cassert>#include <random>#include <functional>#include <stack>#include <iomanip>#include <cassert>#include <boost/multiprecision/cpp_int.hpp>#include <complex>#include <cstdio>#include <list>#include <bitset>//#include <stdio.h>//< in.txt > out.txtusing namespace std;//std::ios::sync_with_stdio(false);//std::cin.tie(0);const long long MOD = 1e9 + 7;const long long INF = 1e18;typedef long long LL;typedef long double LD;typedef boost::multiprecision::cpp_int bigint;typedef pair<LL, LL> PLL;typedef pair<int, int> PI;typedef pair<LD, LL> pdl;typedef pair<LD, LD> pdd;typedef vector<LL> VLL;typedef vector<VLL> VVLL;typedef vector<int> VI;typedef vector<vector<int>> VVI;typedef unsigned long long ULL;template<class T>using pqueue = priority_queue<T, vector<T>, function<bool(T, T)>>;template<class T>inline void chmin(T& a, T b) {a = min(a, b);}template<class T>inline void chmax(T& a, T b) {a = max(a, b);}void input();void solve();void daminput();void naive();void outputinput();int main() {std::cin.tie(0);std::ios::sync_with_stdio(false);input();//daminput();solve();//naive();//outputinput();return 0;}////////////////////////////////////////////////////////////////////////////////////////////////////void input() {}void daminput() {}template<class K>class Matrix {public:vector<vector<K>> v;int H, W;Matrix(int h, int w) :H(h), W(w) {v.resize(h, vector<K>(w, K(0)));}Matrix(vector<K>& v0) {H = v0.size();W = 1;v.resize(H, vector<K>(1, K(0)));for (int y = 0; y < H; y++) {v[y][0] = v0[y];}}Matrix() :H(0), W(0) {}void resize(int h, int w) {H = h;W = w;v.resize(H, vector<K>(W, K(0)));}vector<K>& operator[](int y) {return v[y];}vector<K>& back() {return v.back();}Matrix<K>& operator+=(Matrix<K>& B);Matrix<K>& operator-=(Matrix<K>& B);Matrix<K>& operator*=(Matrix<K>& B);Matrix<K>& operator*=(K k);Matrix<K>& operator/=(K k);};template<class K>Matrix<K> operator+(Matrix<K>& A, Matrix<K>& B) {assert(A.H == B.H && A.W == B.W);int H = A.H;int W = A.W;Matrix<K> C(H, W);for (int y = 0; y < H; y++) {for (int x = 0; x < W; x++) {C[y][x] = A[y][x] + B[y][x];}}return C;}template<class K>Matrix<K> operator-(Matrix<K>& A, Matrix<K>& B) {assert(A.H == B.H && A.W == B.W);int H = A.H;int W = A.W;Matrix<K> C(H, W);for (int y = 0; y < H; y++) {for (int x = 0; x < W; x++) {C[y][x] = A[y][x] - B[y][x];}}return C;}template<class K>Matrix<K> operator*(Matrix<K>& A, Matrix<K>& B) {assert(A.W == B.H);int H = A.H;int W = B.W;Matrix<K> C(H, W);for (int k = 0; k < A.W; k++) {for (int y = 0; y < H; y++) {for (int x = 0; x < W; x++) {C[y][x] += A[y][k] * B[k][x];}}}return C;}template<class K>Matrix<K> operator*(Matrix<K>& A, K k) {int H = A.H;int W = A.W;Matrix<K> C(H, W);for (int y = 0; y < A.H; y++) {for (int x = 0; x < A.W; x++) {C[y][x] = A[y][x] * k;}}return C;}template<class K>Matrix<K> operator*(K k, Matrix<K>& A) {int H = A.H;int W = A.W;Matrix<K> C(H, W);for (int y = 0; y < A.H; y++) {for (int x = 0; x < A.W; x++) {C[y][x] = A[y][x] * k;}}return C;}template<class K>Matrix<K> operator/(Matrix<K>& A, K k) {int H = A.H;int W = A.W;Matrix<K> C(H, W);for (int y = 0; y < A.H; y++) {for (int x = 0; x < A.W; x++) {C[y][x] = A[y][x] / k;}}return C;}template<class K>Matrix<K>& Matrix<K>::operator+=(Matrix<K>& B) {assert(H == B.H && W == B.W);for (int y = 0; y < H; y++) {for (int x = 0; x < W; x++) {v[y][x] += B[y][x];}}return *this;}template<class K>Matrix<K>& Matrix<K>::operator-=(Matrix<K>& B) {assert(H == B.H && W == B.W);for (int y = 0; y < H; y++) {for (int x = 0; x < W; x++) {v[y][x] -= B[y][x];}}return *this;}template<class K>Matrix<K>& Matrix<K>::operator*=(Matrix<K>& B) {*this = *this * B;return *this;}template<class K>Matrix<K>& Matrix<K>::operator*=(K k) {for (int y = 0; y < H; y++) {for (int x = 0; x < W; x++) {v[y][x] *= k;}}return *this;}template<class K>Matrix<K>& Matrix<K>::operator/=(K k) {for (int y = 0; y < H; y++) {for (int x = 0; x < W; x++) {v[y][x] /= k;}}return *this;}template<class K>bool operator==(Matrix<K>& A, Matrix<K>& B) {if (A.H != B.H || A.W != B.W)return false;for (int y = 0; y < A.H; y++) {for (int x = 0; x < A.W; x++) {if (A[y][x] != B[y][x])return false;}}return true;}template<class K>bool operator!=(Matrix<K>& A, Matrix<K>& B) {return !(A == B);}template<class K>Matrix<K> pow(Matrix<K>& A, LL p) {assert(A.H == A.W);if (p == 1)return A;Matrix<K> temp = pow(A, p >> 1);temp *= temp;if (p == 1) {temp *= A;}return temp;}//行列Aを階段行列に変換する//返り値:行列のランクtemplate<class K>int ConvertToStair(Matrix<K>& A) {int H = A.H;int W = A.W;int x = 0, y = 0;while (true) {if (x >= W || y >= H)break;if (A[y][x] == K()) {int yy = y + 1;for (; yy < H; yy++) {if (A[yy][x] != K()) {swap(A[yy], A[y]);for (int xx = x; xx < W; xx++) {A[yy][xx] *= K(-1);}break;}}if (yy == H) {x++;continue;}}for (int yy = y + 1; yy < H; yy++) {K f = A[yy][x] / A[y][x];for (int xx = x; xx < W; xx++) {A[yy][xx] = A[yy][xx] - A[y][xx] * f;}}x++;y++;}return y;}//行列Aを階段行列に変換する//conv[y][x] := 元の行列A_xを何回加えて今のA_yにしたか//返り値:行列のランクtemplate<class K>int ConvertToStair(Matrix<K>& A, vector<vector<K>>& conv) {int H = A.H;int W = A.W;int x = 0, y = 0;conv.resize(H, vector<K>(H, K()));for (int yy = 0; yy < H; yy++) {conv[yy][yy] = K(1);}while (true) {if (x >= W || y >= H)break;if (A[y][x] == K()) {int yy = y + 1;for (; yy < H; yy++) {if (A[yy][x] != K()) {swap(A[yy], A[y]);swap(conv[yy], conv[y]);for (int xx = x; xx < W; xx++) {A[yy][xx] *= K(-1);}for (int n = 0; n < H; n++) {conv[yy][n] *= K(-1);}break;}}if (yy == H) {x++;continue;}}for (int yy = y + 1; yy < H; yy++) {K f = A[yy][x] / A[y][x];for (int xx = x; xx < W; xx++) {A[yy][xx] = A[yy][xx] - A[y][xx] * f;}for (int n = 0; n < H; n++) {conv[yy][n] -= conv[y][n] * f;}}x++;y++;}return y;}//行列式を求めるtemplate<class K>K Determinant(Matrix<K>& A) {ConvertToStair(A);K ans(1);for (int y = 0; y < A.H; y++) {ans *= A[y][y];}return ans;}//線型方程式を解く//返り値:解の有無//particular:特殊解//bases:解空間の基底template<class K>bool SolveLinearEquations(Matrix<K>& A, vector<K>& B, vector<vector<K>>& bases, vector<K>& particular) {int H = A.H;int W = A.W;int X = 0, Y = 0;//階段行列に変形while (true) {if (X >= W || Y >= H)break;if (A[Y][X] == K()) {int y = Y + 1;for (; y < H; y++) {if (A[y][X] != K()) {swap(A[y], A[Y]);swap(B[y], B[Y]);break;}}if (y == H) {X++;continue;}}for (int y = Y + 1; y < H; y++) {K f = A[y][X] / A[Y][X];for (int x = X; x < W; x++) {A[y][x] = A[y][x] - A[Y][x] * f;}B[y] -= B[Y] * f;}X++;Y++;}//元のAのランクと、AにBをくっつけた拡張行列のランクが等しいか確かめるfor (int y = Y; y < H; y++) {if (B[y] != K(0)) {//解は存在しないreturn false;}}int rank = Y;bases.resize(W - rank, vector<K>(W, K(0)));//右上三角行列を作るように列を取っていくparticular.resize(W, K(0));X = 0;Y = 0;VI use; //取る列VI notuse; //取らない列while (X < W && Y < rank) {if (A[Y][X] == K(0)) {notuse.push_back(X);X++;}else {use.push_back(X);X++;Y++;}}while (X < W) {notuse.push_back(X);X++;}//特殊解を求めるfor (int x : notuse) {particular[x] = K(0);}for (int y = rank - 1; y >= 0; y--) {K b = B[y];for (int x = y + 1; x < rank; x++) {b -= A[y][use[x]] * particular[use[x]];}particular[use[y]] = b / A[y][use[y]];}//解空間の基底for (int base = 0; base < W - rank; base++) {vector<K>& v = bases[base];for (int x : notuse) {v[x] = K(0);}v[notuse[base]] = K(1);for (int y = rank - 1; y >= 0; y--) {K b = -1 * A[y][notuse[base]];for (int x = y + 1; x < rank; x++) {b -= A[y][use[x]] * v[use[x]];}v[use[y]] = b / A[y][use[y]];}}return true;}//線型方程式を解く//返り値:解空間の有無//particular:特殊解template<class K>bool SolveLinearEquations(Matrix<K>& A, vector<K>& B, vector<K>& particular) {int H = A.H;int W = A.W;int X = 0, Y = 0;//階段行列に変形while (true) {if (X >= W || Y >= H)break;if (A[Y][X] == K()) {int y = Y + 1;for (; y < H; y++) {if (A[y][X] != K()) {swap(A[y], A[Y]);swap(B[y], B[Y]);break;}}if (y == H) {X++;continue;}}for (int y = Y + 1; y < H; y++) {K f = A[y][X] / A[Y][X];for (int x = X; x < W; x++) {A[y][x] = A[y][x] - A[Y][x] * f;}B[y] -= B[Y] * f;}X++;Y++;}//元のAのランクと、AにBをくっつけた拡張行列のランクが等しいか確かめるfor (int y = Y; y < H; y++) {if (B[y] != K(0)) {//解は存在しないreturn false;}}int rank = Y;//右上三角行列を作るように列を取っていくparticular.resize(W, K(0));X = 0;Y = 0;VI use; //取る列VI notuse; //取らない列while (X < W && Y < rank) {if (A[Y][X] == K(0)) {notuse.push_back(X);X++;}else {use.push_back(X);X++;Y++;}}while (X < W) {notuse.push_back(X);X++;}//特殊解を求めるfor (int x : notuse) {particular[x] = K(0);}for (int y = rank - 1; y >= 0; y--) {K b = B[y];for (int x = y + 1; x < rank; x++) {b -= A[y][use[x]] * particular[use[x]];}particular[use[y]] = b / A[y][use[y]];}return true;}template<class T>struct Gedge {int src, to;T cost;int id;Gedge(int s, int t, T c, int i = -1) :src(s), to(t), cost(c), id(i) {}Gedge(int t, T c) :src(-1), to(t), cost(c), id(-1) {}};template<class T>using WeightedGraph = vector<vector<Gedge<T>>>;using UnweightedGraph = vector<vector<LL>>;template<class T>using Gedges = vector<Gedge<T>>;template<class T>struct TNode {int parent;VI childs;T cost;int id;TNode() :parent(-1), cost(0), id(-1) {};};template<class T>using Tree = vector<TNode<T>>;template<class T>class HLD {public:Tree<T>& tree;LL V;VLL depth; //各頂点が属するHeavy集合の深さVLL top; //各頂点が属するHeavy集合の一番上の頂点VLL in; //各頂点がEuler-TourでどこにいるかVLL out; //各頂点の部分木の終わりHLD(Tree<T>& t, LL root = 0) :tree(t) {V = t.size();VLL subtrees(V, -1);//各部分木のサイズを求める{stack<LL> order;stack<LL> hold;hold.push(root);while (!hold.empty()) {LL cur = hold.top();hold.pop();order.push(cur);for (LL ch : tree[cur].childs) {hold.push(ch);}}while (!order.empty()) {LL cur = order.top();order.pop();subtrees[cur] = 1;for (int& ch : tree[cur].childs) {subtrees[cur] += subtrees[ch];if (subtrees[ch] > subtrees[tree[cur].childs[0]]) {swap(ch, tree[cur].childs[0]);}}}}//HL分解 with eulertour{in.resize(V);out.resize(V);depth.resize(V);top.resize(V);LL cur = root;LL nextid = 0;dfs(cur, nextid);}}void dfs(LL cur, LL& nextind) {in[cur] = nextind++;for (auto ch : tree[cur].childs) {//0番目の子は同じHeavy集合if (ch == tree[cur].childs[0]) {top[ch] = top[cur];depth[ch] = depth[cur];}//それ以外は新しいHeavy集合else {top[ch] = ch;depth[ch] = depth[cur] + 1;}dfs(ch, nextind);}out[cur] = nextind - 1;}LL LCA(LL u, LL v) {//uの属するnode.depth >= vの属するnode.depthにするif (depth[u] < depth[v]) {swap(u, v);}while (depth[u] > depth[v]) {u = tree[top[u]].parent;}while (top[u] != top[v]) {u = tree[top[u]].parent;v = tree[top[v]].parent;}if (in[u] > in[v])return v;else return u;}};template<class Type>void SetTree(WeightedGraph<Type>& G, Tree<Type>& T, int root = 0) {int N = G.size();T.resize(N);queue<int> q;q.push(root);T[root].parent = -1;T[root].id = -1;T[root].cost = 0;while (!q.empty()) {int cur = q.front();q.pop();for (Gedge<Type>& e : G[cur]) {if (e.to == T[cur].parent)continue;T[e.to].parent = cur;T[cur].childs.push_back(e.to);T[e.to].id = e.id;T[e.to].cost = e.cost;q.push(e.to);}}}//TT(T,T):=モノイドの乗算//require Monoidtemplate<class T>class Segtree {private:vector<T> seg;LL RN;typedef function<T(T, T)> TT;TT f;T te;public:Segtree(LL N, TT _f, T e) :te(e) {RN = 1;while (RN < N)RN *= 2;seg.resize(2 * RN, te);f = _f;}Segtree(vector<T>& V, TT _f, T e) :te(e) {LL N = V.size();RN = 1;while (RN < N)RN *= 2;seg.resize(2 * RN, te);f = _f;for (LL n = 0; n < N; n++) seg[RN + n] = V[n];for (LL k = RN - 1; k >= 1; k--) {seg[k] = f(seg[2 * k], seg[2 * k + 1]);}}//set n-th as x(0 index!!!!!)void set(LL n, T x) {seg[RN + n] = x;n = (RN + n) / 2;while (n >= 1) {seg[n] = f(seg[2 * n], seg[2 * n + 1]);n /= 2;}}//change n-th number p to x*p(0 index!!!!!)void addl(LL n, T x) {seg[RN + n] = f(x, seg[RN + n]);n = (RN + n) / 2;while (n >= 1) {seg[n] = f(seg[2 * n], seg[2 * n + 1]);n /= 2;}}//change n-th number p to p*x(0 index!!!!!)void addr(LL n, T x) {seg[RN + n] = f(seg[RN + n], x);n = (RN + n) / 2;while (n >= 1) {seg[n] = f(seg[2 * n], seg[2 * n + 1]);n /= 2;}}//get [l,r] (0 index!!!!!)T get(LL l, LL r) {T ansl = te, ansr = te;r++;l += RN;r += RN;while (l < r) {if (l & 1) {ansl = f(ansl, seg[l]);l++;}if (r & 1) {r--;ansr = f(seg[r], ansr);}l >>= 1;r >>= 1;}return f(ansl, ansr);}//get n-th number(0 index!!!!!)T get(LL n) {return seg[RN + n];}T operator[](LL n) {return seg[RN + n];}};class Modint {public:LL v;Modint(LL _v) {_v %= MOD;if (_v < 0)_v += MOD;v = _v;}Modint operator+=(Modint m);Modint operator-=(Modint m);Modint operator*=(Modint m);Modint operator/=(Modint m);friend ostream& operator<<(ostream& st, const Modint& m);friend istream& operator>>(istream& st, Modint& m);Modint() :v(0) {}static Modint one;};bool operator==(Modint a, Modint b) {return a.v == b.v;}bool operator!=(Modint a, Modint b) {return a.v != b.v;}Modint Modint::one = Modint(1);template<class T>T pow(T& base, LL p) {if (p == 0)return T();else if (p == 1)return base;T ret = pow(base, p / 2);ret *= ret;if (p & 1)ret *= base;return ret;}template<class T>T modpow(T base, LL p) {if (p == 0)return T();else if (p == 1)return base;T ret = modpow(base, p / 2);ret *= ret;if (p & 1)ret *= base;return ret;}ostream& operator<<(ostream& st, const Modint& m) {cout << m.v;return st;}istream& operator>>(istream& st, Modint& m) {LL v;cin >> v;m.v = v % MOD;return st;}Modint operator+(Modint a, Modint b) {Modint r;r.v = a.v + b.v;if (r.v >= MOD)r.v -= MOD;return r;}Modint operator-(Modint a, Modint b) {Modint r;r.v = a.v - b.v;if (r.v < 0)r.v += MOD;return r;}Modint operator*(Modint a, Modint b) {return Modint((a.v * b.v) % MOD);}Modint operator+(Modint a, LL b) {return Modint(a.v + b);}Modint operator+(LL a, Modint b) {return Modint(a + b.v);}Modint operator-(Modint a, LL b) {return Modint(a.v - b);}Modint operator-(LL a, Modint b) {return Modint(a - b.v);}Modint operator*(Modint a, LL b) {return Modint(a.v * (b % MOD));}Modint operator*(LL a, Modint b) {return Modint((a % MOD) * b.v);}Modint operator/(Modint a, Modint b) {return a * modpow(b, MOD - 2);}Modint Modint::operator+=(Modint m) {*this = *this + m;return *this;}Modint Modint::operator-=(Modint m) {*this = *this - m;return *this;}Modint Modint::operator*=(Modint m) {*this = *this * m;return *this;}Modint Modint::operator/=(Modint m) {*this *= modpow(m, MOD - 2);return *this;}//O(min(N-R,R))Modint Comb(LL N, LL R) {if (R > N - R)return Comb(N, N - R);Modint ans((LL)1);for (LL n = N; n > N - R; n--) {ans *= Modint(n);}for (LL n = R; n >= 1; n--) {ans *= modpow(Modint(n), MOD - 2);}return ans;}void solve() {int N;cin >> N;WeightedGraph<int> G(N);VI A(N-1), B(N-1);for (int n = 0; n < N - 1; n++) {int a, b;cin >> a >> b;A[n] = a;B[n] = b;G[a].push_back(Gedge<int>(a, b, 0, n));G[b].push_back(Gedge<int>(b, a, 0, n));}Tree<int> T;SetTree(G, T, 0);HLD<int> hld(T, 0);VI etov(N-1, -1);for (int n = 0; n < N - 1; n++) {int a = A[n];int b = B[n];if (T[a].parent == b) {etov[n] = a;}else {etov[n] = b;}}Matrix<Modint> E(2, 2);E[0][0] = 1;E[0][1] = 0;E[1][0] = 0;E[1][1] = 1;Segtree<Matrix<Modint>> seg(N, [](Matrix<Modint> a, Matrix<Modint> b) {return a * b;}, E);int Q;cin >> Q;for (int q = 0; q < Q; q++) {string type;cin >> type;if (type[0] == 'x') {int i;Modint x00, x01, x10, x11;cin >> i >> x00 >> x01 >> x10 >> x11;i = etov[i];Matrix<Modint> after(2, 2);after[0][0] = x00;after[0][1] = x01;after[1][0] = x10;after[1][1] = x11;int iconv = hld.in[i];seg.set(iconv, after);}else {int i, j;cin >> i >> j;Matrix<Modint> ans = E;while (hld.top[i] != hld.top[j]) {int jtop = hld.top[j];int jconv = hld.in[j];int jtopconv = hld.in[jtop];Matrix<Modint> res = seg.get(jtopconv, jconv);ans = res * ans;j = jtop;j = T[j].parent;}if (i != j) {int jmax = j;while (T[jmax].parent != i) {jmax = T[jmax].parent;}int jconv = hld.in[j];int jmaxconv = hld.in[jmax];Matrix<Modint> res = seg.get(jmaxconv, jconv);ans = res * ans;}cout << ans[0][0] << " " << ans[0][1] << " " << ans[1][0] << " " << ans[1][1] << "\n";}}}void naive() {}void outputinput() {}