CodeChef Strange Transform
問題概要
長さ N の数列 A がある. f(A) は i 番目の要素が A[i] XOR A[i+1] となる数列とする.
Q 個のクエリ (k, x) が与えられるので f^k(A) の x 番目の要素を求めよ.
N ≦ 2e5, Q ≦ 2e5, k ≦ 1e9, x ≦ N
解法
f^k(A)_0 がどの位置の値を XOR したものになるかを観察すると, 2冪ごとに 100....01 みたいな感じになる.
フラクタルっぽい感じ.
なので上のbitから再帰で計算してやると, 各クエリで 2^(bit count(k) ) くらいで求まるけど, それでは全然間に合わない.
よく考えると, kの上の方のbitは関係なくて, 下位18bitだけ見ればよい.
さらに, 前処理で各位置 x について k < (1<<9) で f^k(A)_x を求めておくと, 残りの上 9 bitだけの再帰になるので, 各クエリ 2^9 で間に合う.
つまり計算量 O(N sqrt N+Q sqrt N).
これ log とかで解けたりしないのかな.
ソースコード
https://www.codechef.com/viewsolution/21426207
#include <bits/stdc++.h> using namespace std; const int B = 18; const int hB = B >> 1; const int MAX = 1 << B; int N; int dp[1 << hB][MAX]; int calc(int i, int x) { if (i >= N) return 0; if (x < (1 << hB)) return dp[x][i]; int t = 31 - __builtin_clz(x); int tx = x - (1 << t); return calc(i, tx) ^ calc(i + (1 << t), tx); } int main() { ios::sync_with_stdio(false), cin.tie(0); int Q; cin >> N >> Q; for (int i = 0; i < N; i++) { cin >> dp[0][i]; } for (int j = 1; j < (1 << hB); j++) { for (int i = 0; i < N; i++) { dp[j][i] = dp[j - 1][i] ^ (i + 1 < N ? dp[j - 1][i + 1] : 0); } } while (Q--) { int K, X; cin >> K >> X; --X; K &= (1 << B) - 1; printf("%d\n", calc(X, K)); } return 0; }
CodeChef IMGOD Apun Hi Bhagwan Hai !
問題概要
整数N (1 <= N <= 1e5) のみが与えられる.
分割する対象が区別できるものでの N の分割数 S(N, i) mod 163577857 (1 <= i <= N) をすべて求めよ.
解法
これは第二種スターリング数というものらしい.
S(n, k) = (1 / k!) * Σ(-1)^(k - m) * kCm * m^n = Σ ( (-1)^(k - m) / (k - m)! ) * ( m^n / m! )
という風に変形すると畳み込みの形で表せることがわかります.
なのでFFTをしたい気持ちになるけど値が大きいので誤差が怖い.
実はこの問題の mod の値 163577857 = 39 * 2^22 + 1 は NTT (高速剰余変換) が使える mod であることがググるとわかります. ちなみに最小の原始根は 23
なので整数のまま誤差なく計算できるので安心.
ソースコード
https://www.codechef.com/viewsolution/20267065
#include <bits/stdc++.h> using namespace std; using ll = long long; int mod_inv(ll a, ll m) { ll b = m, u = 1, v = 0; while (b > 0) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return (u % m + m) % m; } ll mod_pow(ll x, ll y, ll md) { ll res = 1; while (y) { if (y & 1) res = res * x % md; x = x * x % md; y >>= 1; } return res; } template <int Mod, int PrimitiveRoot> class fast_modulo_transform { public: static vector<int> fft(vector<int> v, bool inv) { const int N = v.size(); assert((N ^ (N & -N)) == 0); int ww = mod_pow(PrimitiveRoot, (Mod - 1) / N, Mod); if (inv) ww = mod_inv(ww, Mod); for (int m = N; m >= 2; m >>= 1) { const int mh = m >> 1; int w = 1; for (int i = 0; i < mh; ++i) { for (int j = i; j < N; j += m) { const int k = j + mh; int x = v[j] - v[k]; if (x < 0) x += Mod; v[j] += -Mod + v[k]; if (v[j] < 0) v[j] += Mod; v[k] = (1LL * w * x) % Mod; } w = (1LL * w * ww) % Mod; } ww = (1LL * ww * ww) % Mod; } int i = 0; for (int j = 1; j < N - 1; ++j) { for (int k = N >> 1; k > (i ^= k); k >>= 1); if (j < i) swap(v[i], v[j]); } if (inv) { const int inv_n = mod_inv(N, Mod); for (auto& x : v) { x = (1LL * x * inv_n) % Mod; assert(0 <= x && x < Mod); } } return v; } static vector<int> convolution(vector<int> f, vector<int> g) { int sz = 1; const int m = f.size() + g.size() - 1; while (sz < m) sz *= 2; f.resize(sz), g.resize(sz); f = fast_modulo_transform::fft(move(f), false); g = fast_modulo_transform::fft(move(g), false); for (int i = 0; i < sz; ++i) { f[i] = (1LL * f[i] * g[i]) % Mod; } return fast_modulo_transform::fft(move(f), true); } static int get_mod() { return Mod; } }; const ll mod = 163577857; using fmt = fast_modulo_transform<163577857, 23>; int main() { int N; cin >> N; vector<int> tmp(N + 1); tmp[0] = 1; for (int i = 1; i <= N; i++) { tmp[i] = (ll)tmp[i - 1] * i % mod; } tmp[N] = mod_inv(tmp[N], mod); for (int i = N; i >= 1; i--) { tmp[i - 1] = (ll)tmp[i] * i % mod; } vector<int> v1 = tmp, v2 = tmp; for (int i = 0, val = 1; i <= N; i++) { v1[i] = (ll)v1[i] * val % mod; val = (mod - val) % mod; } for (int i = 0; i <= N; i++) { v2[i] = (ll)v2[i] * mod_pow(i, N, mod) % mod; } auto res = fmt::convolution(v1, v2); for (int i = 1; i <= N; i++) { printf("%d%c", res[i], " \n"[i == N]); } return 0; }
感想
これコンテスト中に通したかったなあ (第二種スターリング数であることまではわかってたので)
それはそうと NTT 速すぎてビビった.
HackerRank Drawing Rectangles
問題概要
グリッド内の n 個の長方形を, 列または行を削除する操作によって最小回数で全て消したい.
その最小回数と消すべき列, 行を出力せよ.
ただし長方形の x, y 座標の範囲は [0, 3e5] で, さらに全長方形の和集合の面積は 3e5以下.
解法
和集合の面積が3e5以下であることから, いずれかの長方形に含まれる任意のマスは map を持って平面走査することで列挙することができます.
あとは行と列の二部グラフを作って辺を貼れば, 最小点カバーを求める問題となります.
最小点カバーは最大流を流したあとに, その残余グラフで BFS などを行うことで求めることができるのでOK.
グラフのサイズがかなり大きいですが, 二部グラフの最大マッチングでは dinic なら O(E√V) なので間に合います.
ソースコード
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; struct edge { int to, cap, rev; edge(int to_, int cap_, int rev_) : to(to_), cap(cap_), rev(rev_) {}; }; const int MAX = 3e5 + 1; const int V = MAX * 2 + 2; const int src = MAX * 2, syn = MAX * 2 + 1; vector<edge> G[V]; int level[V]; int iter[V]; void add(int from, int to, int cap) { G[from].emplace_back(to, cap, G[to].size()); G[to].emplace_back(from, 0, G[from].size() - 1); } void bfs(int s) { fill(level, level + V, -1); queue<int> que; level[s] = 0; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (int i = 0; i < (int)G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; que.push(e.to); } } } } int dfs(int v, int t, int f) { if (v == t) return f; for (int &i = iter[v]; i < (int)G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int dinic(int s, int t) { int flow = 0; while (true) { bfs(s); if (level[t] < 0) return flow; fill(iter, iter + V, 0); int f; while ((f = dfs(s, t, INF)) > 0) { flow += f; } } } int main() { ios::sync_with_stdio(false), cin.tie(0); int n; cin >> n; vector<vector<int>> recs; for (int i = 0; i < n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; x2++, y2++; vector<int> v1 = { x1, y1, y2, 1 }; vector<int> v2 = { x2, y1, y2, -1 }; recs.push_back(move(v1)); recs.push_back(move(v2)); } for (int i = 0; i < MAX; i++) { add(src, i, 1); add(MAX + i, syn, 1); } sort(recs.begin(), recs.end()); map<int, int> imo; for (int x = 0, id = 0; x < MAX; x++) { while (id < (int)recs.size() && recs[id][0] == x) { int l = recs[id][1], r = recs[id][2], v = recs[id][3]; imo[l] += v; if (imo[l] == 0) imo.erase(l); imo[r] -= v; if (imo[r] == 0) imo.erase(r); id++; } int cnt = 0, pos = 0; for (auto& p : imo) { if (cnt > 0) { for (int y = pos; y < p.first; y++) { add(x, MAX + y, 1); } } pos = p.first; cnt += p.second; } } int res = dinic(src, syn); vector<int> used(MAX * 2); queue<int> q; for (auto e : G[src]) if (e.cap > 0) { used[e.to] = 1; q.push(e.to); } while (!q.empty()) { auto p = q.front(); q.pop(); for (auto e : G[p]) if (e.to != src && e.to != syn && e.cap > 0 && !used[e.to]) { used[e.to] = 1; q.push(e.to); } } vector<int> xs, ys; for (auto e : G[src]) if (e.cap == 0 && !used[e.to]) { xs.push_back(e.to); } for (auto e : G[syn]) if (e.cap > 0 && used[e.to]) { ys.push_back(e.to - MAX); } cout << res << endl; cout << xs.size() << endl; for (int i = 0; i < (int)xs.size(); i++) { if (i != 0) cout << ' '; cout << xs[i]; } cout << endl; cout << ys.size() << endl; for (int i = 0; i < (int)ys.size(); i++) { if (i != 0) cout << ' '; cout << ys[i]; } cout << endl; return 0; }
感想
二部グラフの最小点カバーのやり方を知らなくてコンテスト本番では解けなかったけど, 面白い問題だと思った.
あと制約が大きいせいで, これフローいけるの?ってなりがち.
小ネタ記事のまとめ
このブログの小ネタ記事をまとめときます
遅延評価 Segment Tree の一般的な実装方法 - kazuma8128’s blog
遅延セグ木の抽象化と非再帰化の話
Mo's Algorithm について - kazuma8128’s blog
Moのアルゴリズムの証明的なのとかメモ書き
非負整数値を扱う Trie について - kazuma8128’s blog
Binary Trie の話
色々な畳み込み - kazuma8128’s blog
高速~~変換とその使い道
巨大modでの掛け算の高速化 (Codeforces Round #259 D Little Pony and Elements of Harmony) - kazuma8128’s blog
long longでオーバーフローする掛け算の mod を高速化
k 番目に小さい値を取得可能な集合を管理するデータ構造 - kazuma8128’s blog
配列/BIT/平方分割/Trie/平衡二分木/謎木とか
区間内の x 未満の値の個数, 区間内の k 番目に小さい値 - kazuma8128’s blog
二次元セグ木とか動的wavelet matrixとか
HL分解で部分木クエリ - kazuma8128’s blog
HL分解とオイラーツアーの合体的な
約数集合でのゼータ変換・メビウス変換的なやつと畳み込み - kazuma8128’s blog
GCDの数え上げのやり方
動的な Segment Tree のテクニック - kazuma8128’s blog
動的セグ木のテクいくつか
約数集合でのゼータ変換・メビウス変換的なやつと畳み込み
昨日の CodeChef の July Lunchtime 2018 に参加したときに思いついたのでメモ.
※何も見ずに書いてるからもしかしたら間違いだらけかもしれないので注意です.
ゼータ変換
競プロで使うゼータ変換(?)は, 各集合について, その上位または下位集合の和を求めるやつです.
式で書くと
g(S) = Σ f(T) (S ⊆ T) または g(S) = Σ f(T) (T ⊆ S)
みたいな感じ.
で, これは集合をビットで管理してるときにも使えるけど, 約数集合とかでも使えるというのが今回の話.
上位集合をまとめる方のゼータ変換を使って以下を行います.
g(x) = Σ f(y) (y は x の倍数)
これで各値の個数 f から, 各値の倍数の個数 g を求めることができます.
実装は単純で, 前処理で各値の約数を列挙しておいて, 小さい値から約数側に足していきます.
ちなみに大きい値からやると重複が起こるのでダメ.
for (int x = 2; x <= MAX; x++) { for (int y : divs[x]) { // divs は最初に列挙しておく if (y != x) { f[y] += f[x]; } } }
メビウス変換
こっちはゼータ変換の逆変換なので, 全操作を逆順にやっていくだけです.
大きい値からやりましょう.
for (int x = MAX; x >= 2; x--) { for (int y : divs[x]) { if (y != x) { f[y] -= f[x]; } } }
畳み込み
普通のやつだと, 二つの列をゼータ変換してからかけ合わせてメビウス変換すると, 上位集合なら積集合の個数, 下位集合なら和集合の個数みたいなのが求まります.
くわしくはこの記事を参照.
色々な畳み込み - kazuma8128’s blog
それを今回のに適用すると, 積集合に相当するものは GCD になります. (下位集合でやれば LCM になりそう)
式で書くとこう.
h(z) = Σ f(x) * g(y) (gcd(x, y) = z)
これをすると, 二つの列の任意のペアの gcd を取るときの, 各 GCD の値に対して個数が求まります.
(ところでこういうのも畳み込みっていえるのかな?よく知らない)
計算量はゼータ変換, メビウス変換の部分がボトルネックで O(X^(3/2)) (Xは最大値) になりますが, 一回前処理しとけば X までの値の約数の個数の和程度しかかからないので結構早くなります.
これを利用すれば以下の問題が解けます.
ただしこの畳み込みをさらにまとめて計算しないといけないので少し難しいですが.
その他
ビットの方の高速ゼータ変換みたいな感じでこれも高速化できたりするのかな.
まあこれでも前処理すれば十分早いけど.
(追記 9/27)
よく考えたら前処理も変換も計算量は O(NlogN) でした. 調和級数になってるので.
Codeforces Round #221 Div.1 D Tree and Queries
問題概要
頂点に色が付いたサイズ N の根付き木がある. 根は 1. 以下の Q 個のクエリに答えよ.
- v k : 頂点 v の部分木に k 個以上含まれるような色の種類数を出力
解法
前に解いたときは木上 Mo で unordered_map を使って解いたけど, 若干不正AC感があったので(0.92s / 1s)
これは実は DSU on Tree というのを使うともっと速く解けます.
DSU on Tree について詳しくはこれ
codeforces.com
イメージは dfs で愚直にやるけど, centroid-path でつながった子のときだけ計算結果を持ち越してくる感じ.
クエリは前処理で各頂点に持たせておいて最後にまとめて答えます.
で, どういう状態を持たせるのかが重要で, 適当に各色のカウントを持つだけでは各クエリの計算に O(N) かかるのでダメ.
各色のカウントをさらに unordered_map とかで持てば, 一応追加/削除 O(1) で各クエリに O(√N) *1で答えられるけどまだ遅い.(ちなみに前に解いたときはこれを使った)
一番良いのは各色のカウントと, 各 k について k 個以上含まれる色の種類数を持たせます.(k=0は適当でいい)
更新ができるのか一瞬不安になりますが, 実は簡単で追加/削除 O(1), クエリ O(1) できます.
これで全体で O(NlogN + Q) になるので安心.
ソースコード
http://codeforces.com/contest/375/submission/40633975
#include <bits/stdc++.h> using namespace std; const int MAX = 1e5; vector<int> G[MAX]; int size[MAX]; void build(int v, int prev) { size[v] = 1; for (auto& p : G[v]) if (p == prev) { if (G[v].back() != p) swap(G[v].back(), p); G[v].pop_back(); break; } for (auto to : G[v]) { build(to, v); size[v] += size[to]; } for (auto& to : G[v]) { if (size[to] > size[G[v].back()]) { swap(to, G[v].back()); } } } struct query { int id, k; query(int i, int k_) : id(i), k(k_) {} }; vector<query> qs[MAX]; int res[MAX]; vector<int> vs[MAX]; int c[MAX]; int cnt[MAX]; int dat[MAX + 1]; void add(int v) { ++cnt[c[v]]; ++dat[cnt[c[v]]]; } void del(int v) { --dat[cnt[c[v]]]; --cnt[c[v]]; } void dfs(int v, bool keep = false) { int hv = G[v].empty() ? -1 : G[v].back(); for (auto to : G[v]) { if (to != hv) { dfs(to); } else { dfs(hv, true); vs[v] = move(vs[hv]); } } add(v); vs[v].push_back(v); for (auto to : G[v]) if (to != hv) { for (auto ver : vs[to]) add(ver); copy(vs[to].begin(), vs[to].end(), back_inserter(vs[v])); } for (auto& q : qs[v]) { res[q.id] = dat[q.k]; } if (!keep) { for (auto ver : vs[v]) del(ver); } } int main() { ios::sync_with_stdio(false), cin.tie(0); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> c[i]; --c[i]; } for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; --u, --v; G[u].push_back(v); G[v].push_back(u); } for (int i = 0; i < m; i++) { int v, k; cin >> v >> k; --v; qs[v].emplace_back(i, k); } build(0, -1); dfs(0); for (int i = 0; i < m; i++) { printf("%d\n", res[i]); } return 0; }
蛇足
DSU on Tree を覚えたので使ってみました.
おそらくこういう問題で DSU on Tree を使う時はマージテクでも同じようにできそう.
個人的にはマージテクより実装は少し楽に感じました.
あと, 部分木に対する木上 Mo とできることがほぼ変わらなさそうなので, こういう問題でなら完全上位互換っぽい.
*1:全ての色のカウントの総和が高々 N だから, カウント数の種類は O(√N) になるため
CodeChef FIBTREE Fibonacci Numbers on Tree
問題概要
サイズNの木がある. 各頂点は値を持っている(初期値0). Q個の以下のクエリをオンラインで処理せよ.
- クエリ1:頂点 x から頂点 y へのパス上の各頂点に順番に fib(0), fib(1), ... , fib(k) のフィボナッチ数列を足す
- クエリ2:頂点 x を根としたときに, 頂点 y の部分木に含まれる頂点の値の和 mod 1e9 + 9 を出力
- クエリ3:頂点 x から頂点 y へのパス上の頂点の値の和 mod 1e9 + 9 を出力
- クエリ4:木全体を x 回目のクエリの直後の状態に戻す
解法
面白いけど, 流石に引くレベルの激ヤバ問題.
HL分解でできる色んなしんどい要素をとにかく詰め込みまくったみたいな感じ.
解法は一言でいうと, 部分木クエリ対応のHL分解をしてから完全永続な遅延セグメントツリーに入れてやる.
クエリ1
HL分解すれば区間にフィボナッチ数列を足すクエリに変換できる.
これは遅延セグメントツリーの各ノードに部分木の和とそのノードに加えたい列の最初の2項を持たせてやれば, そのノードに足す値と下に伝搬する2項が求まる.
このときに最初の2項から長さLの列の和を求めたり, 最初の2項からK個進んだ位置の2項を求める必要があるが, これは最初にN個程度の行列を前処理で求めておいてそれを掛けてやれば重めの O(1) で可能.
よって各クエリ O(logN) できる.
ちなみにこの数列バージョンだけの問題が以下. (これだけでもかなり大変)
http://codeforces.com/contest/446/problem/C
これにHL分解の log が付いてほんとに間に合うの?という気持ちにはなるけど, HL分解の log は速いし TL 5s だからなんとかなる.
さらに, パスクエリなせいで左右の方向も考えないといけないので, 右向きに足される列と左向きに足される列の2個の遅延セグメントツリーを持たないといけなくて大変.
クエリ2
ここでも根を固定しない嫌がらせ.
実は根が固定でなくても結局は根を 1 (1-indexed)にしてHL分解して問題ない.
x = y なら (全体の和) を求めればよい.
x != y で x が y の部分木に含まれないなら普通に (y の部分木の和) を求めればよい.
x != y で x が y の部分木に含まれるなら, y の x 方向への子頂点を z とするとき, (全体の和) - (z の部分木の和) を求めればよい.
この部分木に含まれるかどうかの判定は部分木クエリ対応HL分解(オイラーツアー)なら O(1) で判定可能.
z はHL分解を利用しても求まるし, ダブリングを使っても高々 O(logN) で求まる.
部分木クエリも部分木クエリ対応HL分解ならできる.
部分木クエリ対応HL分解については1つ前の記事を参照.
クエリ3
これはパス上の和を求めるだけなのでHL分解で可能.
クエリ4
ここで唐突な完全永続要素.
まあ先ほどの遅延セグメントツリーを永続に実装すればできる.
一応空間計算量に log が付くけど問題はない.
ソースコード
https://www.codechef.com/viewsolution/19244642
#include <bits/stdc++.h> using namespace std; using ll = long long; template<int MOD> struct mod_int { static const int Mod = MOD; unsigned x; mod_int() : x(0) { } mod_int(int sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; } mod_int(long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; } int get() const { return (int)x; } mod_int &operator+=(mod_int that) { if ((x += that.x) >= MOD) x -= MOD; return *this; } mod_int &operator-=(mod_int that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; } mod_int &operator*=(mod_int that) { x = (unsigned long long)x * that.x % MOD; return *this; } mod_int &operator/=(mod_int that) { return *this *= that.inverse(); } mod_int operator+(mod_int that) const { return mod_int(*this) += that; } mod_int operator-(mod_int that) const { return mod_int(*this) -= that; } mod_int operator*(mod_int that) const { return mod_int(*this) *= that; } mod_int operator/(mod_int that) const { return mod_int(*this) /= that; } mod_int inverse() const { long long a = x, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return mod_int(u); } bool operator==(mod_int that) const { return x == that.x; } }; const int mod = 1e9 + 9; using mint = mod_int<mod>; using pmint = pair<mint, mint>; using vi = vector<int>; using vvi = vector<vector<int>>; vvi prod(const vvi& a, const vvi& b) { assert(a.front().size() == b.size()); int x = a.size(), y = a.front().size(), z = b.front().size(); vvi c(x, vi(z)); for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { for (int k = 0; k < z; k++) { c[i][k] = (c[i][k] + (int)((ll)a[i][j] * b[j][k] % mod)) % mod; } } } return c; } const int MAX = 1 << 17; mint nex_f[MAX + 1][2][2]; mint sum_f[MAX + 1][2]; void init_fib() { vvi nex = { { 0, 1 },{ 1, 1 } }; vvi sum = { { 0, 1, 0 },{ 1, 1, 0 },{ 1, 0, 1 } }; vvi tmp1 = { { 1, 0 },{ 0, 1 } }; nex_f[0][0][0] = 1; nex_f[0][0][1] = 0; nex_f[0][1][0] = 0; nex_f[0][1][1] = 1; for (int i = 1; i <= MAX; i++) { tmp1 = prod(nex, tmp1); for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { nex_f[i][j][k] = tmp1[j][k]; } } } vvi tmp2 = { { 1, 0, 0 },{ 0, 1, 0 },{ 0, 0, 1 } }; sum_f[0][0] = sum_f[0][1] = 0; for (int i = 1; i <= MAX; i++) { tmp2 = prod(sum, tmp2); sum_f[i][0] = tmp2[2][0]; sum_f[i][1] = tmp2[2][1]; } } pmint next_fib(const pmint& a01, int x) { return make_pair(nex_f[x][0][0] * a01.first + nex_f[x][0][1] * a01.second , nex_f[x][1][0] * a01.first + nex_f[x][1][1] * a01.second); } mint sum_fib(const pmint& a01, int x) { return sum_f[x][0] * a01.first + sum_f[x][1] * a01.second; } const pmint id(0, 0); void operator+=(pmint& l, const pmint& r) { l.first += r.first; l.second += r.second; } struct seg_node { mint sum; pmint lazy; seg_node *lch, *rch; seg_node(mint s = 0, const pmint& la = id, seg_node* l = nullptr, seg_node* r = nullptr) : sum(s), lazy(la), lch(l), rch(r) {} }; seg_node* add(seg_node* t, int l, int r, const pmint& val, int lb = 0, int ub = MAX) { if (r <= lb || ub <= l) return t; t = t ? new seg_node(t->sum, t->lazy, t->lch, t->rch) : new seg_node; if (l <= lb && ub <= r) { auto p = next_fib(val, lb - l); t->sum += sum_fib(p, ub - lb); t->lazy += p; return t; } int m = (lb + ub) >> 1; if (t->lazy != id) { t->lch = t->lch ? new seg_node(t->lch->sum, t->lch->lazy, t->lch->lch, t->lch->rch) : new seg_node; t->lch->sum += sum_fib(t->lazy, m - lb); t->lch->lazy += t->lazy; auto p = next_fib(t->lazy, m - lb); t->rch = t->rch ? new seg_node(t->rch->sum, t->rch->lazy, t->rch->lch, t->rch->rch) : new seg_node; t->rch->sum += sum_fib(p, ub - m); t->rch->lazy += p; t->lazy = id; } t->lch = add(t->lch, l, r, val, lb, m); t->rch = add(t->rch, l, r, val, m, ub); t->sum = (t->lch ? t->lch->sum : 0) + (t->rch ? t->rch->sum : 0); return t; } mint find(seg_node* t, int l, int r, pmint lazy = id, int lb = 0, int ub = MAX) { if (ub <= l || r <= lb) return 0; if (!t) { l = max(l, lb); r = min(r, ub); return sum_fib(next_fib(lazy, l - lb), r - l); } if (l <= lb && ub <= r) return t->sum + sum_fib(lazy, ub - lb); lazy += t->lazy; int m = (lb + ub) >> 1; return find(t->lch, l, r, lazy, lb, m) + find(t->rch, l, r, next_fib(lazy, m - lb), m, ub); } class heavy_light_decomposition { const int n; vector<vector<int>> g; vector<int> par, heavy, head, in, out; void dfs1(int rt) { vector<int> size(n, 1); vector<size_t> iter(n); vector<pair<int, int>> stp; stp.reserve(n); stp.emplace_back(rt, -1); while (!stp.empty()) { int v = stp.back().first; if (iter[v] < g[v].size()) { if (g[v][iter[v]] != stp.back().second) { stp.emplace_back(g[v][iter[v]], v); } ++iter[v]; continue; } par[v] = stp.back().second; for (auto& u : g[v]) if (u == par[v]) { if (u != g[v].back()) swap(u, g[v].back()); g[v].pop_back(); break; } for (auto& u : g[v]) { size[v] += size[u]; if (size[u] > size[g[v].front()]) swap(u, g[v].front()); } heavy[v] = g[v].empty() ? -1 : g[v].front(); stp.pop_back(); } } void dfs2(int rt) { int it = 0; vector<size_t> iter(n); vector<int> st; st.reserve(n); st.push_back(rt); while (!st.empty()) { int v = st.back(); if (!iter[v]) in[v] = it++; if (iter[v] < g[v].size()) { int u = g[v][iter[v]]; head[u] = iter[v] ? u : head[v]; st.push_back(u); ++iter[v]; continue; } out[v] = it; st.pop_back(); } } public: heavy_light_decomposition(int n_) : n(n_), g(n), par(n), heavy(n), head(n), in(n), out(n) {} void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build(int rt = 0) { dfs1(rt); head[rt] = rt; dfs2(rt); } int get_id(int v) { return in[v]; } int is_include(int u, int v) { return in[u] <= in[v] && out[v] <= out[u]; } int get_child(int u, int v) { while (head[v] != head[u]) { if (par[head[v]] == u) return head[v]; v = par[head[v]]; } return heavy[u]; } void path_query(int u, int v, function<void(int, int)> f) { while (true) { if (in[u] > in[v]) swap(u, v); f(max(in[head[v]], in[u]), in[v] + 1); if (head[u] == head[v]) return; v = par[head[v]]; } } void path_query(int u, int v, function<void(int, int, bool)> f) { vector<pair<int, int>> lc, rc; while (true) { if (in[u] <= in[v]) { rc.emplace_back(max(in[head[v]], in[u]), in[v] + 1); if (head[u] == head[v]) break; v = par[head[v]]; } else { lc.emplace_back(max(in[head[u]], in[v]), in[u] + 1); if (head[u] == head[v]) break; u = par[head[u]]; } } reverse(rc.begin(), rc.end()); for (auto& p : lc) f(p.first, p.second, true); for (auto& p : rc) f(p.first, p.second, false); } void subtree_query(int v, function<void(int, int)> f) { f(in[v], out[v]); } }; int main() { ios::sync_with_stdio(false), cin.tie(0); init_fib(); int N, M; cin >> N >> M; heavy_light_decomposition hld(N); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; --u, --v; hld.add_edge(u, v); } hld.build(); vector<seg_node*> lrt(M), rrt(M); seg_node *lr = nullptr, *rr = nullptr; int lastans = 0; for (int qn = 0; qn < M; qn++) { lrt[qn] = lr; rrt[qn] = rr; string com; int x; cin >> com >> x; x ^= lastans; if (com == "A") { int y; cin >> y; --x, --y; pmint val(1, 1); hld.path_query(x, y, [&](int l, int r, bool rev) { if (!rev) { lr = add(lr, l, r, val); } else { rr = add(rr, N - r, N - l, val); } val = next_fib(val, r - l); }); } else if (com == "QS") { int y; cin >> y; --x, --y; mint res = 0; if (x == y) { res = find(lr, 0, N) + find(rr, 0, N); } else if (!hld.is_include(y, x)) { hld.subtree_query(y, [&](int l, int r) { res += find(lr, l, r) + find(rr, N - r, N - l); }); } else { res = find(lr, 0, N) + find(rr, 0, N); int z = hld.get_child(y, x); hld.subtree_query(z, [&](int l, int r) { res -= find(lr, l, r) + find(rr, N - r, N - l); }); } printf("%d\n", lastans = res.get()); } else if (com == "QC") { int y; cin >> y; --x, --y; mint res = 0; hld.path_query(x, y, [&](int l, int r) { res += find(lr, l, r) + find(rr, N - r, N - l); }); printf("%d\n", lastans = res.get()); } else { lr = lrt[x]; rr = rrt[x]; } } return 0; }