結果
問題 | No.3003 多項式の割り算 〜hard〜 |
ユーザー |
|
提出日時 | 2025-01-17 21:33:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 36,575 bytes |
コンパイル時間 | 2,716 ms |
コンパイル使用メモリ | 233,608 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-17 21:34:14 |
合計ジャッジ時間 | 3,514 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
コンパイルメッセージ
main.cpp:1365:33: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 1365 | void edge_update(int s, auto g) | ^~~~ main.cpp:1391:35: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 1391 | bool try_reconnect(int s, auto f) | ^~~~
ソースコード
#ifdef DEVELOPMENT #include "./local.h" #endif // AtCoder用. #ifdef ATCODER // boost. #if __has_include(<boost/multiprecision/cpp_int.hpp>) #include <boost/multiprecision/cpp_int.hpp> using namespace boost::multiprecision; #endif // atcoder. #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using MINT = modint1000000007; #endif #endif // オンラインジャッジ用. #if defined(ONLINE_JUDGE) || defined(EVAL) // bits. #if __has_include(<bits/stdc++.h>) #include <bits/stdc++.h> using namespace std; #endif // ヒューリスティック. #include <chrono> #include <random> using namespace chrono; #endif // テンプレート. #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define rep(i, n) for (ll i = 0; i < (n); ++i) #define REP(i, cc, n) for (ll i = cc; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i <= (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using lll = __int128_t; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; constexpr double pi = 3.141592653589793; constexpr ll smallMOD = 998244353; constexpr ll bigMOD = 1000000007; constexpr ll INF = 1LL << 60; constexpr ll dx[] = {1, 0, -1, 0, 1, -1, -1, 1}; constexpr ll dy[] = {0, 1, 0, -1, 1, 1, -1, -1}; // init. struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(15); } } init; template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; rep(i, vec.size()) { os << vec[i]; if (i != vec.size() - 1) os << ", "; } os << "]"; return os; } template <typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &vec) { os << "["; rep(i, vec.size()) { os << vec[i]; if (i != vec.size() - 1) os << ", "; } os << "]"; return os; } template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } template <typename T> ostream &operator<<(ostream &os, const set<T> &st) { os << "{"; for (auto itr = st.begin(); itr != st.end(); ++itr) { os << *itr; if (next(itr) != st.end()) os << ", "; } os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const set<T, greater<T>> &st) { os << "{"; for (auto itr = st.begin(); itr != st.end(); ++itr) { os << *itr; if (next(itr) != st.end()) os << ", "; } os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st) { os << "{"; for (auto itr = st.begin(); itr != st.end(); ++itr) { os << *itr; if (next(itr) != st.end()) os << ", "; } os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const multiset<T, greater<T>> &st) { os << "{"; for (auto itr = st.begin(); itr != st.end(); ++itr) { os << *itr; if (next(itr) != st.end()) os << ", "; } os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const queue<T> &que) { queue<T> que2 = que; os << "{"; while (!que2.empty()) { os << que2.front(); que2.pop(); if (!que2.empty()) os << ", "; } os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const deque<T> &deq) { os << "{"; rep(i, deq.size()) { os << deq[i]; if (i != deq.size() - 1) os << ", "; } os << "}"; return os; } template <typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &mp) { os << "{"; for (auto itr = mp.begin(); itr != mp.end(); ++itr) { os << *itr; if (next(itr) != mp.end()) os << ", "; } os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const stack<T> &stk) { stack<T> stk2 = stk; os << "{"; while (!stk2.empty()) { os << stk2.top(); stk2.pop(); if (!stk2.empty()) os << ", "; } os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const priority_queue<T> &que) { priority_queue<T> que2 = que; os << "{"; while (!que2.empty()) { os << que2.top(); que2.pop(); if (!que2.empty()) os << ", "; } os << "}"; return os; } template <class T> bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; } template <class T> bool chmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; } template <class T> size_t HashCombine(const size_t seed, const T &v) { return seed ^ (std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2)); } template <class T, class S> struct std::hash<std::pair<T, S>> { size_t operator()(const std::pair<T, S> &keyval) const noexcept { return HashCombine(std::hash<T>()(keyval.first), keyval.second); } }; template <class T> struct std::hash<std::vector<T>> { size_t operator()(const std::vector<T> &keyval) const noexcept { size_t s = 0; for (auto &&v : keyval) s = HashCombine(s, v); return s; } }; template <int N> struct HashTupleCore { template <class Tuple> size_t operator()(const Tuple &keyval) const noexcept { size_t s = HashTupleCore<N - 1>()(keyval); return HashCombine(s, std::get<N - 1>(keyval)); } }; template <> struct HashTupleCore<0> { template <class Tuple> size_t operator()(const Tuple &keyval) const noexcept { return 0; } }; template <class... Args> struct std::hash<std::tuple<Args...>> { size_t operator()(const tuple<Args...> &keyval) const noexcept { return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval); } }; // 約数列挙→O(√N). vector<ll> all_divisors(ll N) { vector<ll> res; for (ll i = 1; i * i <= N; ++i) { if (N % i != 0) continue; res.push_back(i); if (N / i != i) res.push_back(N / i); } sort(res.begin(), res.end()); return res; } // 素因数分解→O(√N). vector<pair<ll, ll>> prime_factorize(ll N) { vector<pair<ll, ll>> res; for (ll p = 2; p * p <= N; ++p) { if (N % p != 0) continue; ll e = 0; while (N % p == 0) { ++e; N /= p; } res.emplace_back(p, e); } if (N != 1) { res.emplace_back(N, 1); } return res; } // 繰り返し二乗法→O(logY). template <class T> T pow_mod(T A, T N, T M) { T res = 1 % M; A %= M; while (N) { if (N & 1) res = (res * A) % M; A = (A * A) % M; N >>= 1; } return res; } // 回文判定→O(N). bool isPalindrome(string str) { ll low = 0; ll high = str.length() - 1; while (low < high) { if (str[low] != str[high]) { return false; } low++; high--; } return true; } map<char, ll> alphabetHash = { {'a', 2}, {'b', 3}, {'c', 5}, {'d', 7}, {'e', 11}, {'f', 13}, {'g', 17}, {'h', 19}, {'i', 23}, {'j', 29}, {'k', 31}, {'l', 37}, {'m', 41}, {'n', 43}, {'o', 47}, {'p', 53}, {'q', 59}, {'r', 61}, {'s', 67}, {'t', 71}, {'u', 73}, {'v', 79}, {'w', 83}, {'x', 89}, {'y', 97}, {'z', 101}, }; // 文字列の数字に対するmod計算→O(|S|). ll string_mod(string s, ll mod) { ll rest = 0; for (char c : s) { ll v = c - '0'; rest = (rest * 10 + v) % mod; } return rest; } // 二次元累積和. struct CumulativeSum2D { vector<vector<ll>> data; CumulativeSum2D(vector<vector<ll>> &source) { ll h = source.size(); ll w = 0; if (h != 0) w = source[0].size(); data.resize(h + 1, vector<ll>(w + 1, 0)); rep(i, h) { rep(j, w) { data[i + 1][j + 1] = source[i][j]; } } rep(i, h + 1) { rep(j, w) { data[i][j + 1] += data[i][j]; } } rep(i, h) { rep(j, w + 1) { data[i + 1][j] += data[i][j]; } } } // (x1,y1)から(x2,y2)までの矩形和→O(1). ll query(ll x1, ll y1, ll x2, ll y2) { return data[x2][y2] - data[x1][y2] - data[x2][y1] + data[x1][y1]; } }; // UnionFind. struct UnionFind { vector<ll> parent; vector<ll> parentSize; UnionFind(ll N) { rep(i, N + 1) { parent.push_back(i); parentSize.push_back(1); } } ll root(ll x) { if (parent[x] == x) return x; parent[x] = root(parent[x]); return parent[x]; } bool unite(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; if (parentSize[x] > parentSize[y]) swap(x, y); parent[x] = y; parentSize[y] += parentSize[x]; return true; } bool same(ll x, ll y) { return root(x) == root(y); } ll size(ll x) { return parentSize[root(x)]; } }; struct RollBackUnionFind { vector<ll> parent; stack<pair<ll, ll>> history; RollBackUnionFind(ll N) { parent.assign(N, -1); } ll root(ll x) { if (parent[x] < 0) return x; return root(parent[x]); } bool unite(ll x, ll y) { x = root(x); y = root(y); history.push({x, parent[x]}); history.push({y, parent[y]}); if (x == y) return false; if (parent[x] > parent[y]) swap(x, y); parent[x] += parent[y]; parent[y] = x; return true; } ll same(ll x, ll y) { return root(x) == root(y); } ll size(ll x) { return (-parent[root(x)]); } void undo() { parent[history.top().first] = history.top().second; history.pop(); parent[history.top().first] = history.top().second; history.pop(); } void snapshot() { while (!history.empty()) history.pop(); } void rollback() { while (!history.empty()) { undo(); } } }; // Math. struct NCR { ll max = 510000, mod = 0; vector<ll> fact, inv, inv_fact; NCR(ll mod = 998244353) { this->mod = mod; fact.resize(max); inv.resize(max); inv_fact.resize(max); fact[0] = 1; fact[1] = 1; inv[0] = 1; inv[1] = 1; inv_fact[0] = 1; inv_fact[1] = 1; for (ll i = 2; i < max; i++) { fact[i] = fact[i - 1] * i % mod; inv[i] = mod - inv[mod % i] * (mod / i) % mod; inv_fact[i] = inv_fact[i - 1] * inv[i] % mod; } } ll nCr(ll n, ll r) { ll x = fact[n]; ll y = inv_fact[n - r]; ll z = inv_fact[r]; if (n < r) return 0; if (n < 0 || r < 0) return 0; return x * ((y * z) % mod) % mod; } }; // Graph. struct Edge { ll to; ll cost; Edge(ll to, ll cost) : to(to), cost(cost) {} bool operator>(const Edge &e) const { return cost > e.cost; } }; struct Graph { vector<vector<Edge>> g; Graph(ll n) { g.resize(n); } ll size() { return g.size(); } void add_edge(ll from, ll to, ll cost = 1) { g[from].push_back(Edge(to, cost)); g[to].push_back(Edge(from, cost)); } void add_directed_edge(ll from, ll to, ll cost = 1) { g[from].push_back(Edge(to, cost)); } pair<ll, vector<ll>> tree_diameter() { function<pair<ll, ll>(ll, ll)> dfs = [&](ll v, ll p) -> pair<ll, ll> { pair<ll, ll> res = {0, v}; for (auto e : g[v]) { if (e.to == p) continue; auto [d, u] = dfs(e.to, v); d += e.cost; if (res.first < d) { res.first = d; res.second = u; } } return res; }; auto [d, u] = dfs(0, -1); auto [d2, v] = dfs(u, -1); vector<ll> path; function<void(ll, ll, ll)> get_path = [&](ll v, ll p, ll u) { if (v == u) { path.push_back(v); return; } for (auto e : g[v]) { if (e.to == p) continue; get_path(e.to, v, u); if (!path.empty()) { path.push_back(v); return; } } }; get_path(u, -1, v); return {d2, path}; } vector<Edge> &operator[](ll v) { return g[v]; } }; struct Dijkstra { vector<ll> dist; vector<ll> prev; // dijkstraを構築 Dijkstra(Graph &g, ll s) { ll n = g.size(); dist.assign(n, INF); prev.assign(n, -1); priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; dist[s] = 0; pq.emplace(dist[s], s); while (!pq.empty()) { auto p = pq.top(); pq.pop(); ll v = p.second; if (dist[v] < p.first) continue; for (auto &e : g[v]) { if (dist[e.to] > dist[v] + e.cost) { dist[e.to] = dist[v] + e.cost; prev[e.to] = v; pq.emplace(dist[e.to], e.to); } } } } // 最小コストを求める ll get_cost(ll to) { return dist[to]; } // 最短経路を求める vector<ll> get_path(ll to) { vector<ll> get_path; for (ll i = to; i != -1; i = prev[i]) { get_path.push_back(i); } reverse(get_path.begin(), get_path.end()); return get_path; } // 到達可能か調べる bool cango(ll to) { return (dist[to] != INF); } }; struct Bellman_ford { vector<ll> dist; vector<ll> prev; ll start; ll size; bool cl = false; // bellman_fordを構築 Bellman_ford(Graph &g, ll s) { start = s; ll n = g.size(); size = n; dist.assign(n, INF); prev.assign(n, -1); vector<ll> counts(n); vector<bool> inqueue(n); queue<ll> q; dist[s] = 0; q.push(s); inqueue[s] = true; while (!q.empty()) { ll from = q.front(); q.pop(); inqueue[from] = false; for (auto &e : g[from]) { ll d = dist[from] + e.cost; if (d < dist[e.to]) { dist[e.to] = d; prev[e.to] = from; if (!inqueue[e.to]) { q.push(e.to); inqueue[e.to] = true; ++counts[e.to]; if (n < counts[e.to]) cl = true; } } } } } // 最小コストを求める ll get_cost(ll to) { return dist[to]; } // 最短経路を求める vector<ll> get_path(ll to) { vector<ll> path; if (dist[to] != INF) { for (ll i = to; i != -1; i = prev[i]) { path.push_back(i); } reverse(path.begin(), path.end()); } return path; } // 到達可能か調べる bool cango(ll to) { return (dist[to] != INF); } // 閉路の有無を調べる bool closed() { return cl; } }; struct Warshall_floyd { vector<vector<ll>> d; vector<vector<ll>> next; bool cl = false; // warshall_floydを構築 Warshall_floyd(Graph &g) { ll n = g.size(); d.resize(n, vector<ll>(n, INF)); next.resize(n, vector<ll>(n, -1)); for (ll i = 0; i < n; i++) { d[i][i] = 0; } for (ll i = 0; i < n; i++) { for (auto e : g[i]) { d[i][e.to] = e.cost; next[i][e.to] = e.to; } } for (ll k = 0; k < n; ++k) { for (ll i = 0; i < n; ++i) { for (ll j = 0; j < n; ++j) { if (d[i][j] > d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; next[i][j] = next[i][k]; } } } } for (ll i = 0; i < n; i++) { if (d[i][i] < 0) { cl = true; break; } } } // 最小コストを求める ll get_cost(ll from, ll to) { return d[from][to]; } // 最短経路を求める vector<ll> get_path(ll from, ll to) { if (d[from][to] == INF) return {}; vector<ll> path; for (ll at = from; at != to; at = next[at][to]) { if (at == -1) return {}; path.push_back(at); } path.push_back(to); return path; } // 到達可能か調べる bool cango(ll from, ll to) { return d[from][to] != INF; } // 負の閉路の有無を調べる bool closed() { return cl; } }; // others. struct Timer { Timer(ll ms) : duration(ms), start_time(steady_clock::now()) {} bool isTimeOver() const { auto current_time = steady_clock::now(); auto elapsed = duration_cast<milliseconds>(current_time - start_time).count(); return elapsed >= duration; } ll duration; steady_clock::time_point start_time; }; class FunctionalGraph { private: const ll V; ll loop_id; vector<ll> nx; void make_loop(const ll st, ll nw, vector<ll> &vec) { while (nx[nw] != st) { vec.push_back(nx[nw]); visit[nx[nw]] = loop_id; nw = nx[nw]; } } ll dfs(ll u, vector<ll> &vec) { visit[u] = -loop_id; ll v = nx[u]; if (visit[v] == -loop_id) { vec.push_back(u), vec.push_back(v); visit[u] = visit[v] = loop_id; make_loop(u, v, vec); loop_id++; return 0; } else if (visit[v] == 0) { const ll res = dfs(v, vec); if (res == 0) return 0; else return visit[u] = res; } return visit[u] = (visit[v] > 0 ? -visit[v] : visit[v]); } void make_graph() { graph.resize(V); for (ll i = 0; i < V; i++) { if (visit[i] < 0) graph[nx[i]].push_back(i); } } public: vector<ll> visit; vector<vector<ll>> loop, graph; FunctionalGraph(const ll node_size) : V(node_size), loop_id(1), nx(V, 0), visit(V, 0) {} void add_edge(ll u, ll v) { nx[u] = v; if (u == nx[u]) visit[u] = loop_id++, loop.push_back({u}); } void solve() { for (ll i = 0; i < V; i++) { if (visit[i] == 0) { vector<ll> vec; dfs(i, vec); if (!vec.empty()) loop.push_back(move(vec)); } } } }; ll non_mod_ncr(ll n, ll r) { ll res = 1; for (ll i = 0; i < r; i++) { res *= (n - i); } for (ll i = 0; i < r; i++) { res /= (i + 1); } return res; } // 前計算O(N log N)、クエリO(log N) struct FastTruthFactorizes { public: ll N_MAX; vector<ll> spf; FastTruthFactorizes(ll N_MAX) { this->N_MAX = N_MAX; spf.resize(N_MAX); rep(i, N_MAX) spf[i] = i; // 調和級数の和でO(N log N). for (ll p = 2; p * p <= N_MAX; p++) { for (int i = p; i < N_MAX; i += p) { if (spf[i] == i) spf[i] = p; } } } // 素因数分解するO(log N). map<ll, ll> factorize(ll n) { map<ll, ll> mp; while (n != 1) { ll p = spf[n]; mp[p]++; n /= p; } return mp; } // 約数を列挙するO(log N). vector<ll> calcDevisors(ll n) { vector<ll> Y; auto mp = factorize(n); vector<pair<ll, ll>> V; for (auto pa : mp) { V.push_back(pa); } dfs(0, 1, Y, V); return Y; } private: void dfs(ll cur_idx, ll cur_val, vector<ll> &Y, vector<pair<ll, ll>> &mp) { ll N = mp.size(); if (cur_idx == N) { Y.push_back(cur_val); return; } ll v = mp[cur_idx].first; ll c = mp[cur_idx].second; ll mul = 1; rep(p, c + 1) { dfs(cur_idx + 1, cur_val * mul, Y, mp); mul *= v; } return; } }; // 素数判定O(1). bool millerRabin(ll num) { if (num == 1) return false; if (num == 2) return true; if (num % 2 == 0) return false; ll d = num - 1; ll s = 0; while (d % 2 == 0) { d /= 2; s++; } vector<ll> primes; if (num < 4759123141LL) { primes = {2, 7, 61}; } else { primes = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; } for (auto &p : primes) { if (p >= num) return true; ll t, x = pow_mod<lll>(p, d, num); if (x != 1) { for (t = 0; t < s; t++) { if (x == num - 1) break; x = lll(x) * x % num; } if (t == s) return false; } } return true; } // エラトステネスの篩O(N log log N). vector<ll> eratosthenes(ll target) { ll limit = sqrtl(target) + 1; vector<bool> primes(target + 1, true); primes[0] = primes[1] = false; for (ll n = 2; n <= limit; ++n) { if (primes[n]) { for (ll multiple = n * 2; multiple <= target; multiple += n) { primes[multiple] = false; } } } vector<ll> result; for (ll i = 0; i <= target; ++i) { if (primes[i]) { result.push_back(i); } } return result; } template <typename T> bool next_combination(const T first, const T last, int k) { const T subset = first + k; if (first == last || first == subset || last == subset) { return false; } T src = subset; while (first != src) { src--; if (*src < *(last - 1)) { T dest = subset; while (*src >= *dest) { dest++; } iter_swap(src, dest); rotate(src + 1, dest + 1, last); rotate(subset, subset + (last - dest) - 1, last); return true; } } rotate(first, subset, last); return false; } template <typename T> class dynamic_connectivity { class euler_tour_tree { public: struct node; using np = node *; using lint = long long; struct node { np ch[2] = {nullptr, nullptr}; np p = nullptr; int l, r, sz; T val = et, sum = et; bool exact; bool child_exact; bool edge_connected = 0; bool child_edge_connected = 0; node() {} node(int l, int r) : l(l), r(r), sz(l == r), exact(l < r), child_exact(l < r) {} bool is_root() { return !p; } }; vector<unordered_map<int, np>> ptr; np get_node(int l, int r) { if (ptr[l].find(r) == ptr[l].end()) ptr[l][r] = new node(l, r); return ptr[l][r]; } np root(np t) { if (!t) return t; while (t->p) t = t->p; return t; } bool same(np s, np t) { if (s) splay(s); if (t) splay(t); return root(s) == root(t); } np reroot(np t) { auto s = split(t); return merge(s.second, s.first); } pair<np, np> split(np s) { splay(s); np t = s->ch[0]; if (t) t->p = nullptr; s->ch[0] = nullptr; return {t, update(s)}; } pair<np, np> split2(np s) { splay(s); np t = s->ch[0]; np u = s->ch[1]; if (t) t->p = nullptr; s->ch[0] = nullptr; if (u) u->p = nullptr; s->ch[1] = nullptr; return {t, u}; } tuple<np, np, np> split(np s, np t) { auto u = split2(s); if (same(u.first, t)) { auto r = split2(t); return make_tuple(r.first, r.second, u.second); } else { auto r = split2(t); return make_tuple(u.first, r.first, r.second); } } template <typename First, typename... Rest> np merge(First s, Rest... t) { return merge(s, merge(t...)); } np merge(np s, np t) { if (!s) return t; if (!t) return s; while (s->ch[1]) s = s->ch[1]; splay(s); s->ch[1] = t; if (t) t->p = s; return update(s); } int size(np t) { return t ? t->sz : 0; } np update(np t) { t->sum = et; if (t->ch[0]) t->sum = fn(t->sum, t->ch[0]->sum); if (t->l == t->r) t->sum = fn(t->sum, t->val); if (t->ch[1]) t->sum = fn(t->sum, t->ch[1]->sum); t->sz = size(t->ch[0]) + (t->l == t->r) + size(t->ch[1]); t->child_edge_connected = (t->ch[0] ? t->ch[0]->child_edge_connected : 0) | (t->edge_connected) | (t->ch[1] ? t->ch[1]->child_edge_connected : 0); t->child_exact = (t->ch[0] ? t->ch[0]->child_exact : 0) | (t->exact) | (t->ch[1] ? t->ch[1]->child_exact : 0); return t; } void push(np t) { // 遅延評価予定 } void rot(np t, bool b) { np x = t->p, y = x->p; if ((x->ch[1 - b] = t->ch[b])) t->ch[b]->p = x; t->ch[b] = x, x->p = t; update(x); update(t); if ((t->p = y)) { if (y->ch[0] == x) y->ch[0] = t; if (y->ch[1] == x) y->ch[1] = t; update(y); } } void splay(np t) { push(t); while (!t->is_root()) { np q = t->p; if (q->is_root()) { push(q), push(t); rot(t, q->ch[0] == t); } else { np r = q->p; push(r), push(q), push(t); bool b = r->ch[0] == q; if (q->ch[1 - b] == t) rot(q, b), rot(t, b); else rot(t, 1 - b), rot(t, b); } } } void debug(np t) { if (!t) return; debug(t->ch[0]); cerr << t->l << "-" << t->r << " "; debug(t->ch[1]); } public: euler_tour_tree() {} euler_tour_tree(int sz) { ptr.resize(sz); for (int i = 0; i < sz; i++) ptr[i][i] = new node(i, i); } int size(int s) { np t = get_node(s, s); splay(t); return t->sz; } bool same(int s, int t) { return same(get_node(s, s), get_node(t, t)); } void set_size(int sz) { ptr.resize(sz); for (int i = 0; i < sz; i++) ptr[i][i] = new node(i, i); } void update(int s, T x) { np t = get_node(s, s); splay(t); t->val = fn(t->val, x); update(t); } void edge_update(int s, auto g) { np t = get_node(s, s); splay(t); function<void(np)> dfs = [&](np t) { assert(t); if (t->l < t->r && t->exact) { splay(t); t->exact = 0; update(t); g(t->l, t->r); return; } if (t->ch[0] && t->ch[0]->child_exact) dfs(t->ch[0]); else dfs(t->ch[1]); }; while (t && t->child_exact) { dfs(t); splay(t); } } bool try_reconnect(int s, auto f) { np t = get_node(s, s); splay(t); function<bool(np)> dfs = [&](np t) -> bool { assert(t); if (t->edge_connected) { splay(t); return f(t->l); } if (t->ch[0] && t->ch[0]->child_edge_connected) return dfs(t->ch[0]); else return dfs(t->ch[1]); }; while (t->child_edge_connected) { if (dfs(t)) return 1; splay(t); } return 0; } void edge_connected_update(int s, bool b) { np t = get_node(s, s); splay(t); t->edge_connected = b; update(t); } bool link(int l, int r) { if (same(l, r)) return 0; merge(reroot(get_node(l, l)), get_node(l, r), reroot(get_node(r, r)), get_node(r, l)); return 1; } bool cut(int l, int r) { if (ptr[l].find(r) == ptr[l].end()) return 0; np s, t, u; tie(s, t, u) = split(get_node(l, r), get_node(r, l)); merge(s, u); np p = ptr[l][r]; np q = ptr[r][l]; ptr[l].erase(r); ptr[r].erase(l); delete p; delete q; return 1; } T get_sum(int p, int v) { cut(p, v); np t = get_node(v, v); splay(t); T res = t->sum; link(p, v); return res; } T get_sum(int s) { np t = get_node(s, s); splay(t); return t->sum; } }; int dep = 1; vector<euler_tour_tree> ett; vector<vector<unordered_set<int>>> edges; int sz; public: dynamic_connectivity(int sz) : sz(sz) { ett.emplace_back(sz); edges.emplace_back(sz); } bool link(int s, int t) { if (s == t) return 0; if (ett[0].link(s, t)) return 1; edges[0][s].insert(t); edges[0][t].insert(s); if (edges[0][s].size() == 1) ett[0].edge_connected_update(s, 1); if (edges[0][t].size() == 1) ett[0].edge_connected_update(t, 1); return 0; } bool same(int s, int t) { return ett[0].same(s, t); } int size(int s) { return ett[0].size(s); } vector<int> get_vertex(int s) { return ett[0].vertex_list(s); } void update(int s, T x) { ett[0].update(s, x); } T get_sum(int s) { return ett[0].get_sum(s); } bool cut(int s, int t) { if (s == t) return 0; for (int i = 0; i < dep; i++) { edges[i][s].erase(t); edges[i][t].erase(s); if (edges[i][s].size() == 0) ett[i].edge_connected_update(s, 0); if (edges[i][t].size() == 0) ett[i].edge_connected_update(t, 0); } for (int i = dep - 1; i >= 0; i--) { if (ett[i].cut(s, t)) { if (dep - 1 == i) { dep++; ett.emplace_back(sz); edges.emplace_back(sz); } return !try_reconnect(s, t, i); } } return 0; } bool try_reconnect(int s, int t, int k) { for (int i = 0; i < k; i++) { ett[i].cut(s, t); } for (int i = k; i >= 0; i--) { if (ett[i].size(s) > ett[i].size(t)) swap(s, t); auto g = [&](int s, int t) { ett[i + 1].link(s, t); }; ett[i].edge_update(s, g); auto f = [&](int x) -> bool { for (auto itr = edges[i][x].begin(); itr != edges[i][x].end();) { auto y = *itr; itr = edges[i][x].erase(itr); edges[i][y].erase(x); if (edges[i][x].size() == 0) ett[i].edge_connected_update(x, 0); if (edges[i][y].size() == 0) ett[i].edge_connected_update(y, 0); if (ett[i].same(x, y)) { edges[i + 1][x].insert(y); edges[i + 1][y].insert(x); if (edges[i + 1][x].size() == 1) ett[i + 1].edge_connected_update(x, 1); if (edges[i + 1][y].size() == 1) ett[i + 1].edge_connected_update(y, 1); } else { for (int j = 0; j <= i; j++) { ett[j].link(x, y); } return 1; } } return 0; }; if (ett[i].try_reconnect(s, f)) return 1; } return 0; } constexpr static T et = T(); constexpr static T fn(T s, T t) { return s + t; } }; int main() { ll a, b; cin >> a >> b; if (b % 3 == 0) { cout << 0 << " " << a << endl; } else if (b % 3 == 1) { cout << a << " " << 0 << endl; } else { cout << -a << " " << -a << endl; } return 0; }