This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb" #include "my_template.hpp" #include "random/random_graph.hpp" #include "graph/tree_walk_generating_function.hpp" #include "poly/fps_div.hpp" using mint = modint998; template <bool ALLOW_LOOP> void test() { FOR(N, 1, 30) { FOR(50) { Graph<int, 0> G(N); vv(mint, mat, N, N); for (auto& [a, b]: random_tree(N)) { G.add(a, b); mat[a][b] = RNG(0, mint::get_mod()); mat[b][a] = RNG(0, mint::get_mod()); } G.build(); if (ALLOW_LOOP) { FOR(v, N) mat[v][v] = RNG(mint::get_mod()); } int s = RNG(0, N), t = RNG(0, N); int LIM = 200; vc<mint> ANS(LIM + 1); vc<mint> dp(N); dp[s] = 1; FOR(k, LIM) { ANS[k] = dp[t]; vc<mint> newdp(N); FOR(a, N) FOR(b, N) newdp[b] += dp[a] * mat[a][b]; swap(dp, newdp); ANS[k + 1] = dp[t]; } auto [f, g] = tree_walk_generating_function<ALLOW_LOOP, mint>( G, s, t, [&](int i, int j) -> mint { return mat[i][j]; }); f.resize(LIM + 1); g.resize(LIM + 1); f = fps_div(f, g); assert(f == ANS); } } } void solve() { int a, b; cin >> a >> b; cout << a + b << '\n'; } signed main() { test<0>(); test<1>(); solve(); return 0; }
#line 1 "test/1_mytest/tree_walk_gf.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/aplusb" #line 1 "my_template.hpp" #if defined(LOCAL) #include <my_template_compiled.hpp> #else // https://codeforces.com/blog/entry/96344 #pragma GCC optimize("Ofast,unroll-loops") // いまの CF だとこれ入れると動かない? // #pragma GCC target("avx2,popcnt") #include <bits/stdc++.h> using namespace std; using ll = long long; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using i128 = __int128; using u128 = unsigned __int128; using f128 = __float128; template <class T> constexpr T infty = 0; template <> constexpr int infty<int> = 1'010'000'000; template <> constexpr ll infty<ll> = 2'020'000'000'000'000'000; template <> constexpr u32 infty<u32> = infty<int>; template <> constexpr u64 infty<u64> = infty<ll>; template <> constexpr i128 infty<i128> = i128(infty<ll>) * 2'000'000'000'000'000'000; template <> constexpr double infty<double> = infty<ll>; template <> constexpr long double infty<long double> = infty<ll>; using pi = pair<ll, ll>; using vi = vector<ll>; template <class T> using vc = vector<T>; template <class T> using vvc = vector<vc<T>>; template <class T> using vvvc = vector<vvc<T>>; template <class T> using vvvvc = vector<vvvc<T>>; template <class T> using vvvvvc = vector<vvvvc<T>>; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; #define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__)) #define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__)))) // https://trap.jp/post/1224/ #define FOR1(a) for (ll _ = 0; _ < ll(a); ++_) #define FOR2(i, a) for (ll i = 0; i < ll(a); ++i) #define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i) #define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c)) #define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i) #define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i) #define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i) #define overload4(a, b, c, d, e, ...) e #define overload3(a, b, c, d, ...) d #define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__) #define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__) #define FOR_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s))) #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define elif else if #define eb emplace_back #define mp make_pair #define mt make_tuple #define fi first #define se second #define stoi stoll int popcnt(int x) { return __builtin_popcount(x); } int popcnt(u32 x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } int popcnt(u64 x) { return __builtin_popcountll(x); } int popcnt_sgn(int x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(ll x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(u64 x) { return (__builtin_parity(x) & 1 ? -1 : 1); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2) int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2) int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template <typename T> T floor(T a, T b) { return a / b - (a % b && (a ^ b) < 0); } template <typename T> T ceil(T x, T y) { return floor(x + y - 1, y); } template <typename T> T bmod(T x, T y) { return x - y * floor(x, y); } template <typename T> pair<T, T> divmod(T x, T y) { T q = floor(x, y); return {q, x - q * y}; } template <typename T, typename U> T SUM(const vector<U> &A) { T sm = 0; for (auto &&a: A) sm += a; return sm; } #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define LB(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define UB(c, x) distance((c).begin(), upper_bound(all(c), (x))) #define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit() template <typename T> T POP(deque<T> &que) { T a = que.front(); que.pop_front(); return a; } template <typename T> T POP(pq<T> &que) { T a = que.top(); que.pop(); return a; } template <typename T> T POP(pqg<T> &que) { T a = que.top(); que.pop(); return a; } template <typename T> T POP(vc<T> &que) { T a = que.back(); que.pop_back(); return a; } template <typename F> ll binary_search(F check, ll ok, ll ng, bool check_ok = true) { if (check_ok) assert(check(ok)); while (abs(ok - ng) > 1) { auto x = (ng + ok) / 2; (check(x) ? ok : ng) = x; } return ok; } template <typename F> double binary_search_real(F check, double ok, double ng, int iter = 100) { FOR(iter) { double x = (ok + ng) / 2; (check(x) ? ok : ng) = x; } return (ok + ng) / 2; } template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } // ? は -1 vc<int> s_to_vi(const string &S, char first_char) { vc<int> A(S.size()); FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); } return A; } template <typename T, typename U> vector<T> cumsum(vector<U> &A, int off = 1) { int N = A.size(); vector<T> B(N + 1); FOR(i, N) { B[i + 1] = B[i] + A[i]; } if (off == 0) B.erase(B.begin()); return B; } // stable sort template <typename T> vector<int> argsort(const vector<T> &A) { vector<int> ids(len(A)); iota(all(ids), 0); sort(all(ids), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); }); return ids; } // A[I[0]], A[I[1]], ... template <typename T> vc<T> rearrange(const vc<T> &A, const vc<int> &I) { vc<T> B(len(I)); FOR(i, len(I)) B[i] = A[I[i]]; return B; } template <typename T, typename... Vectors> void concat(vc<T> &first, const Vectors &... others) { vc<T> &res = first; (res.insert(res.end(), others.begin(), others.end()), ...); } #endif #line 3 "test/1_mytest/tree_walk_gf.test.cpp" #line 2 "graph/base.hpp" template <typename T> struct Edge { int frm, to; T cost; int id; }; template <typename T = int, bool directed = false> struct Graph { static constexpr bool is_directed = directed; int N, M; using cost_type = T; using edge_type = Edge<T>; vector<edge_type> edges; vector<int> indptr; vector<edge_type> csr_edges; vc<int> vc_deg, vc_indeg, vc_outdeg; bool prepared; class OutgoingEdges { public: OutgoingEdges(const Graph* G, int l, int r) : G(G), l(l), r(r) {} const edge_type* begin() const { if (l == r) { return 0; } return &G->csr_edges[l]; } const edge_type* end() const { if (l == r) { return 0; } return &G->csr_edges[r]; } private: const Graph* G; int l, r; }; bool is_prepared() { return prepared; } Graph() : N(0), M(0), prepared(0) {} Graph(int N) : N(N), M(0), prepared(0) {} void build(int n) { N = n, M = 0; prepared = 0; edges.clear(); indptr.clear(); csr_edges.clear(); vc_deg.clear(); vc_indeg.clear(); vc_outdeg.clear(); } void add(int frm, int to, T cost = 1, int i = -1) { assert(!prepared); assert(0 <= frm && 0 <= to && to < N); if (i == -1) i = M; auto e = edge_type({frm, to, cost, i}); edges.eb(e); ++M; } #ifdef FASTIO // wt, off void read_tree(bool wt = false, int off = 1) { read_graph(N - 1, wt, off); } void read_graph(int M, bool wt = false, int off = 1) { for (int m = 0; m < M; ++m) { INT(a, b); a -= off, b -= off; if (!wt) { add(a, b); } else { T c; read(c); add(a, b, c); } } build(); } #endif void build() { assert(!prepared); prepared = true; indptr.assign(N + 1, 0); for (auto&& e: edges) { indptr[e.frm + 1]++; if (!directed) indptr[e.to + 1]++; } for (int v = 0; v < N; ++v) { indptr[v + 1] += indptr[v]; } auto counter = indptr; csr_edges.resize(indptr.back() + 1); for (auto&& e: edges) { csr_edges[counter[e.frm]++] = e; if (!directed) csr_edges[counter[e.to]++] = edge_type({e.to, e.frm, e.cost, e.id}); } } OutgoingEdges operator[](int v) const { assert(prepared); return {this, indptr[v], indptr[v + 1]}; } vc<int> deg_array() { if (vc_deg.empty()) calc_deg(); return vc_deg; } pair<vc<int>, vc<int>> deg_array_inout() { if (vc_indeg.empty()) calc_deg_inout(); return {vc_indeg, vc_outdeg}; } int deg(int v) { if (vc_deg.empty()) calc_deg(); return vc_deg[v]; } int in_deg(int v) { if (vc_indeg.empty()) calc_deg_inout(); return vc_indeg[v]; } int out_deg(int v) { if (vc_outdeg.empty()) calc_deg_inout(); return vc_outdeg[v]; } #ifdef FASTIO void debug() { print("Graph"); if (!prepared) { print("frm to cost id"); for (auto&& e: edges) print(e.frm, e.to, e.cost, e.id); } else { print("indptr", indptr); print("frm to cost id"); FOR(v, N) for (auto&& e: (*this)[v]) print(e.frm, e.to, e.cost, e.id); } } #endif vc<int> new_idx; vc<bool> used_e; // G における頂点 V[i] が、新しいグラフで i になるようにする // {G, es} // sum(deg(v)) の計算量になっていて、 // 新しいグラフの n+m より大きい可能性があるので注意 Graph<T, directed> rearrange(vc<int> V, bool keep_eid = 0) { if (len(new_idx) != N) new_idx.assign(N, -1); int n = len(V); FOR(i, n) new_idx[V[i]] = i; Graph<T, directed> G(n); vc<int> history; FOR(i, n) { for (auto&& e: (*this)[V[i]]) { if (len(used_e) <= e.id) used_e.resize(e.id + 1); if (used_e[e.id]) continue; int a = e.frm, b = e.to; if (new_idx[a] != -1 && new_idx[b] != -1) { history.eb(e.id); used_e[e.id] = 1; int eid = (keep_eid ? e.id : -1); G.add(new_idx[a], new_idx[b], e.cost, eid); } } } FOR(i, n) new_idx[V[i]] = -1; for (auto&& eid: history) used_e[eid] = 0; G.build(); return G; } Graph<T, true> to_directed_tree(int root = -1) { if (root == -1) root = 0; assert(!is_directed && prepared && M == N - 1); Graph<T, true> G1(N); vc<int> par(N, -1); auto dfs = [&](auto& dfs, int v) -> void { for (auto& e: (*this)[v]) { if (e.to == par[v]) continue; par[e.to] = v, dfs(dfs, e.to); } }; dfs(dfs, root); for (auto& e: edges) { int a = e.frm, b = e.to; if (par[a] == b) swap(a, b); assert(par[b] == a); G1.add(a, b, e.cost); } G1.build(); return G1; } private: void calc_deg() { assert(vc_deg.empty()); vc_deg.resize(N); for (auto&& e: edges) vc_deg[e.frm]++, vc_deg[e.to]++; } void calc_deg_inout() { assert(vc_indeg.empty()); vc_indeg.resize(N); vc_outdeg.resize(N); for (auto&& e: edges) { vc_indeg[e.to]++, vc_outdeg[e.frm]++; } } }; #line 2 "random/base.hpp" u64 RNG_64() { static u64 x_ = u64(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()) * 10150724397891781847ULL; x_ ^= x_ << 7; return x_ ^= x_ >> 9; } u64 RNG(u64 lim) { return RNG_64() % lim; } ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); } #line 2 "random/shuffle.hpp" template <typename T> void shuffle(vc<T>& A) { FOR(i, len(A)) { int j = RNG(0, i + 1); if (i != j) swap(A[i], A[j]); } } #line 2 "ds/unionfind/unionfind.hpp" struct UnionFind { int n, n_comp; vc<int> dat; // par or (-size) UnionFind(int n = 0) { build(n); } void build(int m) { n = m, n_comp = m; dat.assign(n, -1); } void reset() { build(n); } int operator[](int x) { while (dat[x] >= 0) { int pp = dat[dat[x]]; if (pp < 0) { return dat[x]; } x = dat[x] = pp; } return x; } ll size(int x) { x = (*this)[x]; return -dat[x]; } bool merge(int x, int y) { x = (*this)[x], y = (*this)[y]; if (x == y) return false; if (-dat[x] < -dat[y]) swap(x, y); dat[x] += dat[y], dat[y] = x, n_comp--; return true; } vc<int> get_all() { vc<int> A(n); FOR(i, n) A[i] = (*this)[i]; return A; } }; #line 5 "random/random_graph.hpp" void random_relabel(int N, vc<pair<int, int>>& G) { shuffle(G); vc<int> A(N); FOR(i, N) A[i] = i; shuffle(A); for (auto& [a, b]: G) a = A[a], b = A[b]; } template <int DIRECTED> vc<pair<int, int>> random_graph(int n, bool simple) { vc<pair<int, int>> G, cand; FOR(a, n) FOR(b, n) { if (simple && a == b) continue; if (!DIRECTED && a > b) continue; cand.eb(a, b); } int m = RNG(0, len(cand) + 1); set<int> ss; FOR(m) { while (1) { int i = RNG(0, len(cand)); if (simple && ss.count(i)) continue; ss.insert(i); auto [a, b] = cand[i]; G.eb(a, b); break; } } random_relabel(n, G); return G; } vc<pair<int, int>> random_tree(int n) { vc<pair<int, int>> G; FOR(i, 1, n) { G.eb(RNG(0, i), i); } random_relabel(n, G); return G; } // EDGE = true: 各辺が唯一のサイクル(関節点でサイクルまたは辺) // EDGE = false: 各頂点が唯一のサイクル(橋でサイクルまたは辺) vc<pair<int, int>> random_cactus(int N, bool EDGE) { if (!EDGE) { // n 頂点を 1 または 3 以上に分割 vvc<int> A; int n = RNG(1, N + 1); vc<int> S(n, 1); int rest = N - n; while (rest > 0) { int k = RNG(0, n); if (S[k] == 1) { if (rest == 1) { S.eb(1), rest = 0; } else { S[k] += 2, rest -= 2; } } else { S[k]++, rest--; } } n = len(S); int p = 0; FOR(i, n) { vc<int> C; FOR(v, p, p + S[i]) C.eb(v); A.eb(C); p += S[i]; } int m = len(A); auto H = random_tree(m); vc<pair<int, int>> G; FOR(i, m) { vc<int>& V = A[i]; if (len(V) == 1) continue; FOR(k, len(V)) { G.eb(V[k], V[(1 + k) % len(V)]); } } for (auto& [c1, c2]: H) { int a = A[c1][RNG(0, len(A[c1]))]; int b = A[c2][RNG(0, len(A[c2]))]; G.eb(a, b); } random_relabel(N, G); return G; } assert(EDGE); if (N == 1) return {}; int n = RNG(1, N); vc<int> S(n, 2); int rest = N - 1 - n; while (rest > 0) { int k = RNG(0, n); S[k]++, --rest; } vvc<int> A; int p = 0; FOR(i, n) { vc<int> C; FOR(v, p, p + S[i]) C.eb(v); A.eb(C); p += S[i]; } assert(p == N + n - 1); UnionFind uf(p); auto H = random_tree(n); for (auto& [c1, c2]: H) { int a = A[c1][RNG(0, len(A[c1]))]; int b = A[c2][RNG(0, len(A[c2]))]; uf.merge(a, b); } vc<int> new_idx(p); int x = 0; FOR(i, p) if (uf[i] == i) new_idx[i] = x++; assert(x == N); FOR(i, p) new_idx[i] = new_idx[uf[i]]; vc<pair<int, int>> G; FOR(i, n) { vc<int>& V = A[i]; for (auto& v: V) v = new_idx[v]; if (len(V) == 2) { G.eb(V[0], V[1]); } else { FOR(k, len(V)) { G.eb(V[k], V[(1 + k) % len(V)]); } } } random_relabel(N, G); return G; } #line 1 "graph/tree_walk_generating_function.hpp" #line 2 "graph/tree.hpp" #line 4 "graph/tree.hpp" // HLD euler tour をとっていろいろ。 template <typename GT> struct Tree { using Graph_type = GT; GT &G; using WT = typename GT::cost_type; int N; vector<int> LID, RID, head, V, parent, VtoE; vc<int> depth; vc<WT> depth_weighted; Tree(GT &G, int r = 0, bool hld = 1) : G(G) { build(r, hld); } void build(int r = 0, bool hld = 1) { if (r == -1) return; // build を遅延したいとき N = G.N; LID.assign(N, -1), RID.assign(N, -1), head.assign(N, r); V.assign(N, -1), parent.assign(N, -1), VtoE.assign(N, -1); depth.assign(N, -1), depth_weighted.assign(N, 0); assert(G.is_prepared()); int t1 = 0; dfs_sz(r, -1, hld); dfs_hld(r, t1); } void dfs_sz(int v, int p, bool hld) { auto &sz = RID; parent[v] = p; depth[v] = (p == -1 ? 0 : depth[p] + 1); sz[v] = 1; int l = G.indptr[v], r = G.indptr[v + 1]; auto &csr = G.csr_edges; // 使う辺があれば先頭にする for (int i = r - 2; i >= l; --i) { if (hld && depth[csr[i + 1].to] == -1) swap(csr[i], csr[i + 1]); } int hld_sz = 0; for (int i = l; i < r; ++i) { auto e = csr[i]; if (depth[e.to] != -1) continue; depth_weighted[e.to] = depth_weighted[v] + e.cost; VtoE[e.to] = e.id; dfs_sz(e.to, v, hld); sz[v] += sz[e.to]; if (hld && chmax(hld_sz, sz[e.to]) && l < i) { swap(csr[l], csr[i]); } } } void dfs_hld(int v, int ×) { LID[v] = times++; RID[v] += LID[v]; V[LID[v]] = v; bool heavy = true; for (auto &&e: G[v]) { if (depth[e.to] <= depth[v]) continue; head[e.to] = (heavy ? head[v] : e.to); heavy = false; dfs_hld(e.to, times); } } vc<int> heavy_path_at(int v) { vc<int> P = {v}; while (1) { int a = P.back(); for (auto &&e: G[a]) { if (e.to != parent[a] && head[e.to] == v) { P.eb(e.to); break; } } if (P.back() == a) break; } return P; } int heavy_child(int v) { int k = LID[v] + 1; if (k == N) return -1; int w = V[k]; return (parent[w] == v ? w : -1); } int e_to_v(int eid) { auto e = G.edges[eid]; return (parent[e.frm] == e.to ? e.frm : e.to); } int v_to_e(int v) { return VtoE[v]; } int get_eid(int u, int v) { if (parent[u] != v) swap(u, v); assert(parent[u] == v); return VtoE[u]; } int ELID(int v) { return 2 * LID[v] - depth[v]; } int ERID(int v) { return 2 * RID[v] - depth[v] - 1; } // 目標地点へ進む個数が k int LA(int v, int k) { assert(k <= depth[v]); while (1) { int u = head[v]; if (LID[v] - k >= LID[u]) return V[LID[v] - k]; k -= LID[v] - LID[u] + 1; v = parent[u]; } } int la(int u, int v) { return LA(u, v); } int LCA(int u, int v) { for (;; v = parent[head[v]]) { if (LID[u] > LID[v]) swap(u, v); if (head[u] == head[v]) return u; } } int meet(int a, int b, int c) { return LCA(a, b) ^ LCA(a, c) ^ LCA(b, c); } int lca(int u, int v) { return LCA(u, v); } int subtree_size(int v, int root = -1) { if (root == -1) return RID[v] - LID[v]; if (v == root) return N; int x = jump(v, root, 1); if (in_subtree(v, x)) return RID[v] - LID[v]; return N - RID[x] + LID[x]; } int dist(int a, int b) { int c = LCA(a, b); return depth[a] + depth[b] - 2 * depth[c]; } WT dist_weighted(int a, int b) { int c = LCA(a, b); return depth_weighted[a] + depth_weighted[b] - WT(2) * depth_weighted[c]; } // a is in b bool in_subtree(int a, int b) { return LID[b] <= LID[a] && LID[a] < RID[b]; } int jump(int a, int b, ll k) { if (k == 1) { if (a == b) return -1; return (in_subtree(b, a) ? LA(b, depth[b] - depth[a] - 1) : parent[a]); } int c = LCA(a, b); int d_ac = depth[a] - depth[c]; int d_bc = depth[b] - depth[c]; if (k > d_ac + d_bc) return -1; if (k <= d_ac) return LA(a, k); return LA(b, d_ac + d_bc - k); } vc<int> collect_child(int v) { vc<int> res; for (auto &&e: G[v]) if (e.to != parent[v]) res.eb(e.to); return res; } vc<int> collect_light(int v) { vc<int> res; bool skip = true; for (auto &&e: G[v]) if (e.to != parent[v]) { if (!skip) res.eb(e.to); skip = false; } return res; } vc<pair<int, int>> get_path_decomposition(int u, int v, bool edge) { // [始点, 終点] の"閉"区間列。 vc<pair<int, int>> up, down; while (1) { if (head[u] == head[v]) break; if (LID[u] < LID[v]) { down.eb(LID[head[v]], LID[v]); v = parent[head[v]]; } else { up.eb(LID[u], LID[head[u]]); u = parent[head[u]]; } } if (LID[u] < LID[v]) down.eb(LID[u] + edge, LID[v]); elif (LID[v] + edge <= LID[u]) up.eb(LID[u], LID[v] + edge); reverse(all(down)); up.insert(up.end(), all(down)); return up; } // 辺の列の情報 (frm,to,str) // str = "heavy_up", "heavy_down", "light_up", "light_down" vc<tuple<int, int, string>> get_path_decomposition_detail(int u, int v) { vc<tuple<int, int, string>> up, down; while (1) { if (head[u] == head[v]) break; if (LID[u] < LID[v]) { if (v != head[v]) down.eb(head[v], v, "heavy_down"), v = head[v]; down.eb(parent[v], v, "light_down"), v = parent[v]; } else { if (u != head[u]) up.eb(u, head[u], "heavy_up"), u = head[u]; up.eb(u, parent[u], "light_up"), u = parent[u]; } } if (LID[u] < LID[v]) down.eb(u, v, "heavy_down"); elif (LID[v] < LID[u]) up.eb(u, v, "heavy_up"); reverse(all(down)); concat(up, down); return up; } vc<int> restore_path(int u, int v) { vc<int> P; for (auto &&[a, b]: get_path_decomposition(u, v, 0)) { if (a <= b) { FOR(i, a, b + 1) P.eb(V[i]); } else { FOR_R(i, b, a + 1) P.eb(V[i]); } } return P; } // path [a,b] と [c,d] の交わり. 空ならば {-1,-1}. // https://codeforces.com/problemset/problem/500/G pair<int, int> path_intersection(int a, int b, int c, int d) { int ab = lca(a, b), ac = lca(a, c), ad = lca(a, d); int bc = lca(b, c), bd = lca(b, d), cd = lca(c, d); int x = ab ^ ac ^ bc, y = ab ^ ad ^ bd; // meet(a,b,c), meet(a,b,d) if (x != y) return {x, y}; int z = ac ^ ad ^ cd; if (x != z) x = -1; return {x, x}; } // uv path 上で check(v) を満たす最後の v // なければ (つまり check(v) が ng )-1 template <class F> int max_path(F check, int u, int v) { if (!check(u)) return -1; auto pd = get_path_decomposition(u, v, false); for (auto [a, b]: pd) { if (!check(V[a])) return u; if (check(V[b])) { u = V[b]; continue; } int c = binary_search([&](int c) -> bool { return check(V[c]); }, a, b, 0); return V[c]; } return u; } }; #line 2 "graph/ds/static_toptree.hpp" /* 参考 joitour tatyam クラスタは根が virtual なもののみであるような簡易版 N 個の (頂+辺) をマージしていって,木全体+根から親への辺とする. single(v) : v とその親辺を合わせたクラスタ rake(L,R) : L の boundary を維持 compress(L,R) (top-down) 順に x,y */ template <typename TREE> struct Static_TopTree { int N; TREE &tree; vc<int> par, lch, rch, A, B; // A, B boundary (top-down) vc<bool> is_compress; Static_TopTree(TREE &tree) : tree(tree) { build(); } void build() { N = tree.N; par.assign(N, -1), lch.assign(N, -1), rch.assign(N, -1), A.assign(N, -1), B.assign(N, -1), is_compress.assign(N, 0); FOR(v, N) { A[v] = tree.parent[v], B[v] = v; } build_dfs(tree.V[0]); assert(len(par) == 2 * N - 1); } // 木全体での集約値を得る // single(v) : v とその親辺を合わせたクラスタ // rake(x, y, u, v) uv(top down) が boundary になるように rake (maybe v=-1) // compress(x,y,a,b,c) (top-down) 順に (a,b] + (b,c] template <typename TREE_DP, typename F> typename TREE_DP::value_type tree_dp(F single) { using Data = typename TREE_DP::value_type; auto dfs = [&](auto &dfs, int k) -> Data { if (0 <= k && k < N) return single(k); Data x = dfs(dfs, lch[k]), y = dfs(dfs, rch[k]); if (is_compress[k]) { assert(B[lch[k]] == A[rch[k]]); return TREE_DP::compress(x, y); } return TREE_DP::rake(x, y); }; return dfs(dfs, 2 * N - 2); } private: int new_node(int l, int r, int a, int b, bool c) { int v = len(par); par.eb(-1), lch.eb(l), rch.eb(r), A.eb(a), B.eb(b), is_compress.eb(c); par[l] = par[r] = v; return v; } // height, node idx // compress 参考:https://atcoder.jp/contests/abc351/editorial/9910 // ただし heavy path の選び方までは考慮しない pair<int, int> build_dfs(int v) { assert(tree.head[v] == v); auto path = tree.heavy_path_at(v); vc<pair<int, int>> stack; stack.eb(0, path[0]); auto merge_last_two = [&]() -> void { auto [h2, k2] = POP(stack); auto [h1, k1] = POP(stack); stack.eb(max(h1, h2) + 1, new_node(k1, k2, A[k1], B[k2], true)); }; FOR(i, 1, len(path)) { pqg<pair<int, int>> que; int k = path[i]; que.emplace(0, k); for (auto &c: tree.collect_light(path[i - 1])) { que.emplace(build_dfs(c)); } while (len(que) >= 2) { auto [h1, i1] = POP(que); auto [h2, i2] = POP(que); if (i2 == k) swap(i1, i2); int i3 = new_node(i1, i2, A[i1], B[i1], false); if (k == i1) k = i3; que.emplace(max(h1, h2) + 1, i3); } stack.eb(POP(que)); while (1) { int n = len(stack); if (n >= 3 && (stack[n - 3].fi == stack[n - 2].fi || stack[n - 3].fi <= stack[n - 1].fi)) { auto [h3, k3] = POP(stack); merge_last_two(), stack.eb(h3, k3); } elif (n >= 2 && stack[n - 2].fi <= stack[n - 1].fi) { merge_last_two(); } else break; } } while (len(stack) >= 2) { merge_last_two(); } return POP(stack); } }; #line 3 "graph/shortest_path/bfs01.hpp" template <typename T, typename GT> pair<vc<T>, vc<int>> bfs01(GT& G, int v) { assert(G.is_prepared()); int N = G.N; vc<T> dist(N, infty<T>); vc<int> par(N, -1); deque<int> que; dist[v] = 0; que.push_front(v); while (!que.empty()) { auto v = que.front(); que.pop_front(); for (auto&& e: G[v]) { if (dist[e.to] == infty<T> || dist[e.to] > dist[e.frm] + e.cost) { dist[e.to] = dist[e.frm] + e.cost; par[e.to] = e.frm; if (e.cost == 0) que.push_front(e.to); else que.push_back(e.to); } } } return {dist, par}; } // 多点スタート。[dist, par, root] template <typename T, typename GT> tuple<vc<T>, vc<int>, vc<int>> bfs01(GT& G, vc<int> vs) { assert(G.is_prepared()); int N = G.N; vc<T> dist(N, infty<T>); vc<int> par(N, -1); vc<int> root(N, -1); deque<int> que; for (auto&& v: vs) { dist[v] = 0; root[v] = v; que.push_front(v); } while (!que.empty()) { auto v = que.front(); que.pop_front(); for (auto&& e: G[v]) { if (dist[e.to] == infty<T> || dist[e.to] > dist[e.frm] + e.cost) { dist[e.to] = dist[e.frm] + e.cost; root[e.to] = root[e.frm]; par[e.to] = e.frm; if (e.cost == 0) que.push_front(e.to); else que.push_back(e.to); } } } return {dist, par, root}; } #line 2 "mod/modint_common.hpp" struct has_mod_impl { template <class T> static auto check(T &&x) -> decltype(x.get_mod(), std::true_type{}); template <class T> static auto check(...) -> std::false_type; }; template <class T> class has_mod : public decltype(has_mod_impl::check<T>(std::declval<T>())) {}; template <typename mint> mint inv(int n) { static const int mod = mint::get_mod(); static vector<mint> dat = {0, 1}; assert(0 <= n); if (n >= mod) n %= mod; while (len(dat) <= n) { int k = len(dat); int q = (mod + k - 1) / k; dat.eb(dat[k * q - mod] * mint::raw(q)); } return dat[n]; } template <typename mint> mint fact(int n) { static const int mod = mint::get_mod(); assert(0 <= n && n < mod); static vector<mint> dat = {1, 1}; while (len(dat) <= n) dat.eb(dat[len(dat) - 1] * mint::raw(len(dat))); return dat[n]; } template <typename mint> mint fact_inv(int n) { static vector<mint> dat = {1, 1}; if (n < 0) return mint(0); while (len(dat) <= n) dat.eb(dat[len(dat) - 1] * inv<mint>(len(dat))); return dat[n]; } template <class mint, class... Ts> mint fact_invs(Ts... xs) { return (mint(1) * ... * fact_inv<mint>(xs)); } template <typename mint, class Head, class... Tail> mint multinomial(Head &&head, Tail &&... tail) { return fact<mint>(head) * fact_invs<mint>(std::forward<Tail>(tail)...); } template <typename mint> mint C_dense(int n, int k) { assert(n >= 0); if (k < 0 || n < k) return 0; static vvc<mint> C; static int H = 0, W = 0; auto calc = [&](int i, int j) -> mint { if (i == 0) return (j == 0 ? mint(1) : mint(0)); return C[i - 1][j] + (j ? C[i - 1][j - 1] : 0); }; if (W <= k) { FOR(i, H) { C[i].resize(k + 1); FOR(j, W, k + 1) { C[i][j] = calc(i, j); } } W = k + 1; } if (H <= n) { C.resize(n + 1); FOR(i, H, n + 1) { C[i].resize(W); FOR(j, W) { C[i][j] = calc(i, j); } } H = n + 1; } return C[n][k]; } template <typename mint, bool large = false, bool dense = false> mint C(ll n, ll k) { assert(n >= 0); if (k < 0 || n < k) return 0; if constexpr (dense) return C_dense<mint>(n, k); if constexpr (!large) return multinomial<mint>(n, k, n - k); k = min(k, n - k); mint x(1); FOR(i, k) x *= mint(n - i); return x * fact_inv<mint>(k); } template <typename mint, bool large = false> mint C_inv(ll n, ll k) { assert(n >= 0); assert(0 <= k && k <= n); if (!large) return fact_inv<mint>(n) * fact<mint>(k) * fact<mint>(n - k); return mint(1) / C<mint, 1>(n, k); } // [x^d](1-x)^{-n} template <typename mint, bool large = false, bool dense = false> mint C_negative(ll n, ll d) { assert(n >= 0); if (d < 0) return mint(0); if (n == 0) { return (d == 0 ? mint(1) : mint(0)); } return C<mint, large, dense>(n + d - 1, d); } #line 3 "mod/modint.hpp" template <int mod> struct modint { static constexpr u32 umod = u32(mod); static_assert(umod < u32(1) << 31); u32 val; static modint raw(u32 v) { modint x; x.val = v; return x; } constexpr modint() : val(0) {} constexpr modint(u32 x) : val(x % umod) {} constexpr modint(u64 x) : val(x % umod) {} constexpr modint(u128 x) : val(x % umod) {} constexpr modint(int x) : val((x %= mod) < 0 ? x + mod : x){}; constexpr modint(ll x) : val((x %= mod) < 0 ? x + mod : x){}; constexpr modint(i128 x) : val((x %= mod) < 0 ? x + mod : x){}; bool operator<(const modint &other) const { return val < other.val; } modint &operator+=(const modint &p) { if ((val += p.val) >= umod) val -= umod; return *this; } modint &operator-=(const modint &p) { if ((val += umod - p.val) >= umod) val -= umod; return *this; } modint &operator*=(const modint &p) { val = u64(val) * p.val % umod; return *this; } modint &operator/=(const modint &p) { *this *= p.inverse(); return *this; } modint operator-() const { return modint::raw(val ? mod - val : u32(0)); } modint operator+(const modint &p) const { return modint(*this) += p; } modint operator-(const modint &p) const { return modint(*this) -= p; } modint operator*(const modint &p) const { return modint(*this) *= p; } modint operator/(const modint &p) const { return modint(*this) /= p; } bool operator==(const modint &p) const { return val == p.val; } bool operator!=(const modint &p) const { return val != p.val; } modint inverse() const { int a = val, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b), swap(u -= t * v, v); } return modint(u); } modint pow(ll n) const { assert(n >= 0); modint ret(1), mul(val); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } static constexpr int get_mod() { return mod; } // (n, r), r は 1 の 2^n 乗根 static constexpr pair<int, int> ntt_info() { if (mod == 120586241) return {20, 74066978}; if (mod == 167772161) return {25, 17}; if (mod == 469762049) return {26, 30}; if (mod == 754974721) return {24, 362}; if (mod == 880803841) return {23, 211}; if (mod == 943718401) return {22, 663003469}; if (mod == 998244353) return {23, 31}; if (mod == 1004535809) return {21, 582313106}; if (mod == 1012924417) return {21, 368093570}; return {-1, -1}; } static constexpr bool can_ntt() { return ntt_info().fi != -1; } }; #ifdef FASTIO template <int mod> void rd(modint<mod> &x) { fastio::rd(x.val); x.val %= mod; // assert(0 <= x.val && x.val < mod); } template <int mod> void wt(modint<mod> x) { fastio::wt(x.val); } #endif using modint107 = modint<1000000007>; using modint998 = modint<998244353>; #line 2 "mod/mod_inv.hpp" // long でも大丈夫 // (val * x - 1) が mod の倍数になるようにする // 特に mod=0 なら x=0 が満たす ll mod_inv(ll val, ll mod) { if (mod == 0) return 0; mod = abs(mod); val %= mod; if (val < 0) val += mod; ll a = val, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b), swap(u -= t * v, v); } if (u < 0) u += mod; return u; } #line 2 "mod/crt3.hpp" constexpr u32 mod_pow_constexpr(u64 a, u64 n, u32 mod) { a %= mod; u64 res = 1; FOR(32) { if (n & 1) res = res * a % mod; a = a * a % mod, n /= 2; } return res; } template <typename T, u32 p0, u32 p1> T CRT2(u64 a0, u64 a1) { static_assert(p0 < p1); static constexpr u64 x0_1 = mod_pow_constexpr(p0, p1 - 2, p1); u64 c = (a1 - a0 + p1) * x0_1 % p1; return a0 + c * p0; } template <typename T, u32 p0, u32 p1, u32 p2> T CRT3(u64 a0, u64 a1, u64 a2) { static_assert(p0 < p1 && p1 < p2); static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1); static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2); static constexpr u64 p01 = u64(p0) * p1; u64 c = (a1 - a0 + p1) * x1 % p1; u64 ans_1 = a0 + c * p0; c = (a2 - ans_1 % p2 + p2) * x2 % p2; return T(ans_1) + T(c) * T(p01); } template <typename T, u32 p0, u32 p1, u32 p2, u32 p3> T CRT4(u64 a0, u64 a1, u64 a2, u64 a3) { static_assert(p0 < p1 && p1 < p2 && p2 < p3); static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1); static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2); static constexpr u64 x3 = mod_pow_constexpr(u64(p0) * p1 % p3 * p2 % p3, p3 - 2, p3); static constexpr u64 p01 = u64(p0) * p1; u64 c = (a1 - a0 + p1) * x1 % p1; u64 ans_1 = a0 + c * p0; c = (a2 - ans_1 % p2 + p2) * x2 % p2; u128 ans_2 = ans_1 + c * static_cast<u128>(p01); c = (a3 - ans_2 % p3 + p3) * x3 % p3; return T(ans_2) + T(c) * T(p01) * T(p2); } template <typename T, u32 p0, u32 p1, u32 p2, u32 p3, u32 p4> T CRT5(u64 a0, u64 a1, u64 a2, u64 a3, u64 a4) { static_assert(p0 < p1 && p1 < p2 && p2 < p3 && p3 < p4); static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1); static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2); static constexpr u64 x3 = mod_pow_constexpr(u64(p0) * p1 % p3 * p2 % p3, p3 - 2, p3); static constexpr u64 x4 = mod_pow_constexpr(u64(p0) * p1 % p4 * p2 % p4 * p3 % p4, p4 - 2, p4); static constexpr u64 p01 = u64(p0) * p1; static constexpr u64 p23 = u64(p2) * p3; u64 c = (a1 - a0 + p1) * x1 % p1; u64 ans_1 = a0 + c * p0; c = (a2 - ans_1 % p2 + p2) * x2 % p2; u128 ans_2 = ans_1 + c * static_cast<u128>(p01); c = static_cast<u64>(a3 - ans_2 % p3 + p3) * x3 % p3; u128 ans_3 = ans_2 + static_cast<u128>(c * p2) * p01; c = static_cast<u64>(a4 - ans_3 % p4 + p4) * x4 % p4; return T(ans_3) + T(c) * T(p01) * T(p23); } #line 2 "poly/convolution_naive.hpp" template <class T, typename enable_if<!has_mod<T>::value>::type* = nullptr> vc<T> convolution_naive(const vc<T>& a, const vc<T>& b) { int n = int(a.size()), m = int(b.size()); if (n > m) return convolution_naive<T>(b, a); if (n == 0) return {}; vector<T> ans(n + m - 1); FOR(i, n) FOR(j, m) ans[i + j] += a[i] * b[j]; return ans; } template <class T, typename enable_if<has_mod<T>::value>::type* = nullptr> vc<T> convolution_naive(const vc<T>& a, const vc<T>& b) { int n = int(a.size()), m = int(b.size()); if (n > m) return convolution_naive<T>(b, a); if (n == 0) return {}; vc<T> ans(n + m - 1); if (n <= 16 && (T::get_mod() < (1 << 30))) { for (int k = 0; k < n + m - 1; ++k) { int s = max(0, k - m + 1); int t = min(n, k + 1); u64 sm = 0; for (int i = s; i < t; ++i) { sm += u64(a[i].val) * (b[k - i].val); } ans[k] = sm; } } else { for (int k = 0; k < n + m - 1; ++k) { int s = max(0, k - m + 1); int t = min(n, k + 1); u128 sm = 0; for (int i = s; i < t; ++i) { sm += u64(a[i].val) * (b[k - i].val); } ans[k] = T::raw(sm % T::get_mod()); } } return ans; } #line 2 "poly/convolution_karatsuba.hpp" // 任意の環でできる template <typename T> vc<T> convolution_karatsuba(const vc<T>& f, const vc<T>& g) { const int thresh = 30; if (min(len(f), len(g)) <= thresh) return convolution_naive(f, g); int n = max(len(f), len(g)); int m = ceil(n, 2); vc<T> f1, f2, g1, g2; if (len(f) < m) f1 = f; if (len(f) >= m) f1 = {f.begin(), f.begin() + m}; if (len(f) >= m) f2 = {f.begin() + m, f.end()}; if (len(g) < m) g1 = g; if (len(g) >= m) g1 = {g.begin(), g.begin() + m}; if (len(g) >= m) g2 = {g.begin() + m, g.end()}; vc<T> a = convolution_karatsuba(f1, g1); vc<T> b = convolution_karatsuba(f2, g2); FOR(i, len(f2)) f1[i] += f2[i]; FOR(i, len(g2)) g1[i] += g2[i]; vc<T> c = convolution_karatsuba(f1, g1); vc<T> F(len(f) + len(g) - 1); assert(2 * m + len(b) <= len(F)); FOR(i, len(a)) F[i] += a[i], c[i] -= a[i]; FOR(i, len(b)) F[2 * m + i] += b[i], c[i] -= b[i]; if (c.back() == T(0)) c.pop_back(); FOR(i, len(c)) if (c[i] != T(0)) F[m + i] += c[i]; return F; } #line 2 "poly/ntt.hpp" template <class mint> void ntt(vector<mint>& a, bool inverse) { assert(mint::can_ntt()); const int rank2 = mint::ntt_info().fi; const int mod = mint::get_mod(); static array<mint, 30> root, iroot; static array<mint, 30> rate2, irate2; static array<mint, 30> rate3, irate3; assert(rank2 != -1 && len(a) <= (1 << max(0, rank2))); static bool prepared = 0; if (!prepared) { prepared = 1; root[rank2] = mint::ntt_info().se; iroot[rank2] = mint(1) / root[rank2]; FOR_R(i, rank2) { root[i] = root[i + 1] * root[i + 1]; iroot[i] = iroot[i + 1] * iroot[i + 1]; } mint prod = 1, iprod = 1; for (int i = 0; i <= rank2 - 2; i++) { rate2[i] = root[i + 2] * prod; irate2[i] = iroot[i + 2] * iprod; prod *= iroot[i + 2]; iprod *= root[i + 2]; } prod = 1, iprod = 1; for (int i = 0; i <= rank2 - 3; i++) { rate3[i] = root[i + 3] * prod; irate3[i] = iroot[i + 3] * iprod; prod *= iroot[i + 3]; iprod *= root[i + 3]; } } int n = int(a.size()); int h = topbit(n); assert(n == 1 << h); if (!inverse) { int len = 0; while (len < h) { if (h - len == 1) { int p = 1 << (h - len - 1); mint rot = 1; FOR(s, 1 << len) { int offset = s << (h - len); FOR(i, p) { auto l = a[i + offset]; auto r = a[i + offset + p] * rot; a[i + offset] = l + r; a[i + offset + p] = l - r; } rot *= rate2[topbit(~s & -~s)]; } len++; } else { int p = 1 << (h - len - 2); mint rot = 1, imag = root[2]; for (int s = 0; s < (1 << len); s++) { mint rot2 = rot * rot; mint rot3 = rot2 * rot; int offset = s << (h - len); for (int i = 0; i < p; i++) { u64 mod2 = u64(mod) * mod; u64 a0 = a[i + offset].val; u64 a1 = u64(a[i + offset + p].val) * rot.val; u64 a2 = u64(a[i + offset + 2 * p].val) * rot2.val; u64 a3 = u64(a[i + offset + 3 * p].val) * rot3.val; u64 a1na3imag = (a1 + mod2 - a3) % mod * imag.val; u64 na2 = mod2 - a2; a[i + offset] = a0 + a2 + a1 + a3; a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3)); a[i + offset + 2 * p] = a0 + na2 + a1na3imag; a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag); } rot *= rate3[topbit(~s & -~s)]; } len += 2; } } } else { mint coef = mint(1) / mint(len(a)); FOR(i, len(a)) a[i] *= coef; int len = h; while (len) { if (len == 1) { int p = 1 << (h - len); mint irot = 1; FOR(s, 1 << (len - 1)) { int offset = s << (h - len + 1); FOR(i, p) { u64 l = a[i + offset].val; u64 r = a[i + offset + p].val; a[i + offset] = l + r; a[i + offset + p] = (mod + l - r) * irot.val; } irot *= irate2[topbit(~s & -~s)]; } len--; } else { int p = 1 << (h - len); mint irot = 1, iimag = iroot[2]; FOR(s, (1 << (len - 2))) { mint irot2 = irot * irot; mint irot3 = irot2 * irot; int offset = s << (h - len + 2); for (int i = 0; i < p; i++) { u64 a0 = a[i + offset + 0 * p].val; u64 a1 = a[i + offset + 1 * p].val; u64 a2 = a[i + offset + 2 * p].val; u64 a3 = a[i + offset + 3 * p].val; u64 x = (mod + a2 - a3) * iimag.val % mod; a[i + offset] = a0 + a1 + a2 + a3; a[i + offset + 1 * p] = (a0 + mod - a1 + x) * irot.val; a[i + offset + 2 * p] = (a0 + a1 + 2 * mod - a2 - a3) * irot2.val; a[i + offset + 3 * p] = (a0 + 2 * mod - a1 - x) * irot3.val; } irot *= irate3[topbit(~s & -~s)]; } len -= 2; } } } } #line 8 "poly/convolution.hpp" template <class mint> vector<mint> convolution_ntt(vector<mint> a, vector<mint> b) { if (a.empty() || b.empty()) return {}; int n = int(a.size()), m = int(b.size()); int sz = 1; while (sz < n + m - 1) sz *= 2; // sz = 2^k のときの高速化。分割統治的なやつで損しまくるので。 if ((n + m - 3) <= sz / 2) { auto a_last = a.back(), b_last = b.back(); a.pop_back(), b.pop_back(); auto c = convolution(a, b); c.resize(n + m - 1); c[n + m - 2] = a_last * b_last; FOR(i, len(a)) c[i + len(b)] += a[i] * b_last; FOR(i, len(b)) c[i + len(a)] += b[i] * a_last; return c; } a.resize(sz), b.resize(sz); bool same = a == b; ntt(a, 0); if (same) { b = a; } else { ntt(b, 0); } FOR(i, sz) a[i] *= b[i]; ntt(a, 1); a.resize(n + m - 1); return a; } template <typename mint> vector<mint> convolution_garner(const vector<mint>& a, const vector<mint>& b) { int n = len(a), m = len(b); if (!n || !m) return {}; static constexpr int p0 = 167772161; static constexpr int p1 = 469762049; static constexpr int p2 = 754974721; using mint0 = modint<p0>; using mint1 = modint<p1>; using mint2 = modint<p2>; vc<mint0> a0(n), b0(m); vc<mint1> a1(n), b1(m); vc<mint2> a2(n), b2(m); FOR(i, n) a0[i] = a[i].val, a1[i] = a[i].val, a2[i] = a[i].val; FOR(i, m) b0[i] = b[i].val, b1[i] = b[i].val, b2[i] = b[i].val; auto c0 = convolution_ntt<mint0>(a0, b0); auto c1 = convolution_ntt<mint1>(a1, b1); auto c2 = convolution_ntt<mint2>(a2, b2); vc<mint> c(len(c0)); FOR(i, n + m - 1) { c[i] = CRT3<mint, p0, p1, p2>(c0[i].val, c1[i].val, c2[i].val); } return c; } vector<ll> convolution(vector<ll> a, vector<ll> b) { int n = len(a), m = len(b); if (!n || !m) return {}; if (min(n, m) <= 2500) return convolution_naive(a, b); ll mi_a = MIN(a), mi_b = MIN(b); for (auto& x: a) x -= mi_a; for (auto& x: b) x -= mi_b; assert(MAX(a) * MAX(b) <= 1e18); auto Ac = cumsum<ll>(a), Bc = cumsum<ll>(b); vi res(n + m - 1); for (int k = 0; k < n + m - 1; ++k) { int s = max(0, k - m + 1); int t = min(n, k + 1); res[k] += (t - s) * mi_a * mi_b; res[k] += mi_a * (Bc[k - s + 1] - Bc[k - t + 1]); res[k] += mi_b * (Ac[t] - Ac[s]); } static constexpr u32 MOD1 = 1004535809; static constexpr u32 MOD2 = 1012924417; using mint1 = modint<MOD1>; using mint2 = modint<MOD2>; vc<mint1> a1(n), b1(m); vc<mint2> a2(n), b2(m); FOR(i, n) a1[i] = a[i], a2[i] = a[i]; FOR(i, m) b1[i] = b[i], b2[i] = b[i]; auto c1 = convolution_ntt<mint1>(a1, b1); auto c2 = convolution_ntt<mint2>(a2, b2); FOR(i, n + m - 1) { res[i] += CRT2<u64, MOD1, MOD2>(c1[i].val, c2[i].val); } return res; } template <typename mint> vc<mint> convolution(const vc<mint>& a, const vc<mint>& b) { int n = len(a), m = len(b); if (!n || !m) return {}; if (mint::can_ntt()) { if (min(n, m) <= 50) return convolution_karatsuba<mint>(a, b); return convolution_ntt(a, b); } if (min(n, m) <= 200) return convolution_karatsuba<mint>(a, b); return convolution_garner(a, b); } #line 5 "graph/characteristic_polynomial_of_tree_adjacency_matrix.hpp" template <typename mint> struct TREE_ADJ_MATRIX_DP { using poly = vc<mint>; using Data = array<array<poly, 2>, 2>; using value_type = Data; static void add(poly& f, poly g) { if (len(f) < len(g)) f.resize(len(g)); FOR(i, len(g)) f[i] += g[i]; }; static Data rake(Data L, Data R) { Data Z; add(Z[0][0], convolution(L[0][0], R[0][1])); add(Z[0][1], convolution(L[0][1], R[0][1])); add(Z[1][0], convolution(L[0][0], R[1][1])); add(Z[1][1], convolution(L[0][1], R[1][1])); add(Z[1][0], convolution(L[1][0], R[0][1])); add(Z[1][1], convolution(L[1][1], R[0][1])); return Z; } static Data compress(Data L, Data R) { Data Z; FOR(p, 2) FOR(q, 2) FOR(r, 2) { add(Z[p][r], convolution<mint>(L[p][q], R[1 - q][r])); } return Z; } }; // det(I-xA) の計算 (固有多項式の reverse になっている) // weight(i,j):A[i][j] // 偶数次だけしか出てこないので loop ありより高速 template <typename mint, typename F> vc<mint> characteristic_poly_of_tree_adjacency_matrix_not_allow_loop(Graph<int, 0>& G, F weight) { using poly = vc<mint>; Tree<Graph<int, 0>> tree(G); Static_TopTree<decltype(tree)> STT(tree); // u, v はもう計算したか using Data = array<array<poly, 2>, 2>; auto single = [&](int v) -> Data { Data X; int p = tree.parent[v]; mint wt = (p == -1 ? mint(0) : weight(p, v) * weight(v, p)); X[0][0] = poly{mint(1)}; X[0][1] = poly{mint(1)}; // loop if (p != -1) X[1][1] = poly{mint(0), -wt}; // match return X; }; Data X = STT.tree_dp<TREE_ADJ_MATRIX_DP<mint>>(single); vc<mint> ANS(G.N + 1); FOR(i, len(X[0][1])) { ANS[2 * i] += X[0][1][i]; } return ANS; } template <typename mint, typename F> vc<mint> characteristic_poly_of_tree_adjacency_matrix_allow_loop(Graph<int, 0>& G, F weight) { using poly = vc<mint>; Tree<Graph<int, 0>> tree(G); Static_TopTree<decltype(tree)> STT(tree); using Data = array<array<poly, 2>, 2>; auto single = [&](int v) -> Data { Data X; int p = tree.parent[v]; mint wt = (p == -1 ? mint(0) : weight(p, v) * weight(v, p)); X[0][0] = poly{mint(1)}; X[0][1] = poly{mint(1), -weight(v, v)}; // loop if (p != -1) X[1][1] = poly{mint(0), mint(0), -wt}; // match return X; }; Data X = STT.tree_dp<TREE_ADJ_MATRIX_DP<mint>>(single); vc<mint> ANS(G.N + 1); FOR(i, len(X[0][1])) { ANS[i] += X[0][1][i]; } return ANS; } // det(I-xA) の計算 (固有多項式の reverse になっている) // weight(i,j):A[i][j] template <bool ALLOW_LOOP, typename mint, typename F> vc<mint> characteristic_poly_of_tree_adjacency_matrix(Graph<int, 0>& G, F weight) { if constexpr (ALLOW_LOOP) { return characteristic_poly_of_tree_adjacency_matrix_allow_loop<mint>(G, weight); } else { return characteristic_poly_of_tree_adjacency_matrix_not_allow_loop<mint>(G, weight); } } #line 2 "poly/convolution_all.hpp" #line 2 "poly/ntt_doubling.hpp" #line 4 "poly/ntt_doubling.hpp" // 2^k 次多項式の長さ 2^k が与えられるので 2^k+1 にする template <typename mint, bool transposed = false> void ntt_doubling(vector<mint>& a) { static array<mint, 30> root; static bool prepared = 0; if (!prepared) { prepared = 1; const int rank2 = mint::ntt_info().fi; root[rank2] = mint::ntt_info().se; FOR_R(i, rank2) { root[i] = root[i + 1] * root[i + 1]; } } if constexpr (!transposed) { const int M = (int)a.size(); auto b = a; ntt(b, 1); mint r = 1, zeta = root[topbit(2 * M)]; FOR(i, M) b[i] *= r, r *= zeta; ntt(b, 0); copy(begin(b), end(b), back_inserter(a)); } else { const int M = len(a) / 2; vc<mint> tmp = {a.begin(), a.begin() + M}; a = {a.begin() + M, a.end()}; transposed_ntt(a, 0); mint r = 1, zeta = root[topbit(2 * M)]; FOR(i, M) a[i] *= r, r *= zeta; transposed_ntt(a, 1); FOR(i, M) a[i] += tmp[i]; } } #line 5 "poly/convolution_all.hpp" template <typename T> vc<T> convolution_all(vc<vc<T>>& polys) { if (len(polys) == 0) return {T(1)}; while (1) { int n = len(polys); if (n == 1) break; int m = ceil(n, 2); FOR(i, m) { if (2 * i + 1 == n) { polys[i] = polys[2 * i]; } else { polys[i] = convolution(polys[2 * i], polys[2 * i + 1]); } } polys.resize(m); } return polys[0]; } // product of 1-A[i]x template <typename mint> vc<mint> convolution_all_1(vc<mint> A) { if (!mint::can_ntt()) { vvc<mint> polys; for (auto& a: A) polys.eb(vc<mint>({mint(1), -a})); return convolution_all(polys); } int D = 6; using poly = vc<mint>; int n = 1; while (n < len(A)) n *= 2; int k = topbit(n); vc<mint> F(n), nxt_F(n); FOR(i, len(A)) F[i] = -A[i]; FOR(d, k) { int b = 1 << d; if (d < D) { fill(all(nxt_F), mint(0)); for (int L = 0; L < n; L += 2 * b) { FOR(i, b) FOR(j, b) { nxt_F[L + i + j] += F[L + i] * F[L + b + j]; } FOR(i, b) nxt_F[L + b + i] += F[L + i] + F[L + b + i]; } } elif (d == D) { for (int L = 0; L < n; L += 2 * b) { poly f1 = {F.begin() + L, F.begin() + L + b}; poly f2 = {F.begin() + L + b, F.begin() + L + 2 * b}; f1.resize(2 * b), f2.resize(2 * b), ntt(f1, 0), ntt(f2, 0); FOR(i, b) nxt_F[L + i] = f1[i] * f2[i] + f1[i] + f2[i]; FOR(i, b, 2 * b) nxt_F[L + i] = f1[i] * f2[i] - f1[i] - f2[i]; } } else { for (int L = 0; L < n; L += 2 * b) { poly f1 = {F.begin() + L, F.begin() + L + b}; poly f2 = {F.begin() + L + b, F.begin() + L + 2 * b}; ntt_doubling(f1), ntt_doubling(f2); FOR(i, b) nxt_F[L + i] = f1[i] * f2[i] + f1[i] + f2[i]; FOR(i, b, 2 * b) nxt_F[L + i] = f1[i] * f2[i] - f1[i] - f2[i]; } } swap(F, nxt_F); } if (k - 1 >= D) ntt(F, 1); F.eb(1), reverse(all(F)); F.resize(len(A) + 1); return F; } #line 4 "graph/tree_walk_generating_function.hpp" // ループなし:1600ms(N=10^5) // ループあり:3300ms(N=10^5) template <bool ALLOW_LOOP, typename mint, typename F> pair<vc<mint>, vc<mint>> tree_walk_generating_function(Graph<int, 0>& G, int s, int t, F weight) { int N = G.N; // 分母 auto f = characteristic_poly_of_tree_adjacency_matrix<ALLOW_LOOP, mint>(G, weight); // 分子 // (s,t) パスに沿って成分をかけたものの符号調整 + 他の成分 using poly = vc<mint>; vc<poly> polys; pair<int, mint> path_poly = {0, mint(1)}; vc<bool> on_path(N); auto [dist, par] = bfs01<int>(G, s); on_path[t] = 1; while (t != s) { mint w = weight(par[t], t); t = par[t], on_path[t] = 1; path_poly.fi += 1, path_poly.se *= w; // +wx } UnionFind uf(N); for (auto& e: G.edges) { if (on_path[e.frm] || on_path[e.to]) continue; uf.merge(e.frm, e.to); } vvc<int> comp(N); FOR(v, N) comp[uf[v]].eb(v); FOR(r, N) { if (on_path[r] || uf[r] != r) continue; vc<int>& V = comp[r]; Graph<int, 0> H = G.rearrange(V); poly f = characteristic_poly_of_tree_adjacency_matrix<ALLOW_LOOP, mint>(H, [&](int i, int j) -> mint { return weight(V[i], V[j]); }); polys.eb(f); } poly B = convolution_all<mint>(polys); int m = path_poly.fi; poly g(len(B) + m); FOR(i, len(B)) g[m + i] = path_poly.se * B[i]; return {g, f}; } #line 2 "poly/fps_div.hpp" #line 2 "poly/count_terms.hpp" template<typename mint> int count_terms(const vc<mint>& f){ int t = 0; FOR(i, len(f)) if(f[i] != mint(0)) ++t; return t; } #line 4 "poly/fps_inv.hpp" template <typename mint> vc<mint> fps_inv_sparse(const vc<mint>& f) { int N = len(f); vc<pair<int, mint>> dat; FOR(i, 1, N) if (f[i] != mint(0)) dat.eb(i, f[i]); vc<mint> g(N); mint g0 = mint(1) / f[0]; g[0] = g0; FOR(n, 1, N) { mint rhs = 0; for (auto&& [k, fk]: dat) { if (k > n) break; rhs -= fk * g[n - k]; } g[n] = rhs * g0; } return g; } template <typename mint> vc<mint> fps_inv_dense_ntt(const vc<mint>& F) { vc<mint> G = {mint(1) / F[0]}; ll N = len(F), n = 1; G.reserve(N); while (n < N) { vc<mint> f(2 * n), g(2 * n); FOR(i, min(N, 2 * n)) f[i] = F[i]; FOR(i, n) g[i] = G[i]; ntt(f, false), ntt(g, false); FOR(i, 2 * n) f[i] *= g[i]; ntt(f, true); FOR(i, n) f[i] = 0; ntt(f, false); FOR(i, 2 * n) f[i] *= g[i]; ntt(f, true); FOR(i, n, min(N, 2 * n)) G.eb(-f[i]); n *= 2; } return G; } template <typename mint> vc<mint> fps_inv_dense(const vc<mint>& F) { if (mint::can_ntt()) return fps_inv_dense_ntt(F); const int N = len(F); vc<mint> R = {mint(1) / F[0]}; vc<mint> p; int m = 1; while (m < N) { p = convolution(R, R); p.resize(m + m); vc<mint> f = {F.begin(), F.begin() + min(m + m, N)}; p = convolution(p, f); R.resize(m + m); FOR(i, m + m) R[i] = R[i] + R[i] - p[i]; m += m; } R.resize(N); return R; } template <typename mint> vc<mint> fps_inv(const vc<mint>& f) { assert(f[0] != mint(0)); int n = count_terms(f); int t = (mint::can_ntt() ? 160 : 820); return (n <= t ? fps_inv_sparse<mint>(f) : fps_inv_dense<mint>(f)); } #line 5 "poly/fps_div.hpp" // f/g. f の長さで出力される. template <typename mint, bool SPARSE = false> vc<mint> fps_div(vc<mint> f, vc<mint> g) { if (SPARSE || count_terms(g) < 200) return fps_div_sparse(f, g); int n = len(f); g.resize(n); g = fps_inv<mint>(g); f = convolution(f, g); f.resize(n); return f; } // f/g ただし g は sparse template <typename mint> vc<mint> fps_div_sparse(vc<mint> f, vc<mint>& g) { if (g[0] != mint(1)) { mint cf = g[0].inverse(); for (auto&& x: f) x *= cf; for (auto&& x: g) x *= cf; } vc<pair<int, mint>> dat; FOR(i, 1, len(g)) if (g[i] != mint(0)) dat.eb(i, -g[i]); FOR(i, len(f)) { for (auto&& [j, x]: dat) { if (i >= j) f[i] += x * f[i - j]; } } return f; } #line 7 "test/1_mytest/tree_walk_gf.test.cpp" using mint = modint998; template <bool ALLOW_LOOP> void test() { FOR(N, 1, 30) { FOR(50) { Graph<int, 0> G(N); vv(mint, mat, N, N); for (auto& [a, b]: random_tree(N)) { G.add(a, b); mat[a][b] = RNG(0, mint::get_mod()); mat[b][a] = RNG(0, mint::get_mod()); } G.build(); if (ALLOW_LOOP) { FOR(v, N) mat[v][v] = RNG(mint::get_mod()); } int s = RNG(0, N), t = RNG(0, N); int LIM = 200; vc<mint> ANS(LIM + 1); vc<mint> dp(N); dp[s] = 1; FOR(k, LIM) { ANS[k] = dp[t]; vc<mint> newdp(N); FOR(a, N) FOR(b, N) newdp[b] += dp[a] * mat[a][b]; swap(dp, newdp); ANS[k + 1] = dp[t]; } auto [f, g] = tree_walk_generating_function<ALLOW_LOOP, mint>( G, s, t, [&](int i, int j) -> mint { return mat[i][j]; }); f.resize(LIM + 1); g.resize(LIM + 1); f = fps_div(f, g); assert(f == ANS); } } } void solve() { int a, b; cin >> a >> b; cout << a + b << '\n'; } signed main() { test<0>(); test<1>(); solve(); return 0; }