結果
問題 | No.2699 Simple Math (Returned) |
ユーザー | anmichi |
提出日時 | 2024-08-11 20:35:39 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 21,221 bytes |
コンパイル時間 | 4,839 ms |
コンパイル使用メモリ | 215,732 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-08-11 20:35:51 |
合計ジャッジ時間 | 8,989 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | WA | - |
testcase_02 | AC | 322 ms
5,376 KB |
testcase_03 | AC | 275 ms
5,376 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < n; i++) #define all(v) v.begin(), v.end() template <class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true; } return false; } template <class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true; } return false; } constexpr int INF = 1001001001; constexpr int64_t llINF = 3000000000000000000; const double pi = acos(-1); struct linear_sieve { vector<int> least_factor, prime_list; linear_sieve(int n) : least_factor(n + 1, 0) { for (int i = 2; i <= n; i++) { if (least_factor[i] == 0) { least_factor[i] = i; prime_list.push_back(i); } for (int p : prime_list) { if (ll(i) * p > n || p > least_factor[i]) break; least_factor[i * p] = p; } } } }; template <int modulo> struct modint { int x; modint() : x(0) {} modint(int64_t y) : x(y >= 0 ? y % modulo : (modulo - (-y) % modulo) % modulo) {} modint &operator+=(const modint &p) { if ((x += p.x) >= modulo) x -= modulo; return *this; } modint &operator-=(const modint &p) { if ((x += modulo - p.x) >= modulo) x -= modulo; return *this; } modint &operator*=(const modint &p) { x = (int)(1LL * x * p.x % modulo); return *this; } modint &operator/=(const modint &p) { *this *= p.inv(); return *this; } modint operator-() const { return modint(-x); } 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 x == p.x; } bool operator!=(const modint &p) const { return x != p.x; } modint inv() const { int a = x, b = modulo, 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(int64_t n) const { modint ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const modint &p) { return os << p.x; } friend istream &operator>>(istream &is, modint &a) { int64_t t; is >> t; a = modint<modulo>(t); return (is); } int val() const { return x; } static constexpr int mod() { return modulo; } static constexpr int half() { return (modulo + 1) >> 1; } }; ll extgcd(ll a, ll b, ll &x, ll &y) { // ax+by=gcd(|a|,|b|) if (a < 0 || b < 0) { ll d = extgcd(abs(a), abs(b), x, y); if (a < 0) x = -x; if (b < 0) y = -y; return d; } if (b == 0) { x = 1; y = 0; return a; } ll d = extgcd(b, a % b, y, x); y -= a / b * x; return d; } template <typename T> struct Binomial { vector<T> inv, fact, factinv; Binomial(int n) { inv.resize(n + 1); fact.resize(n + 1); factinv.resize(n + 1); inv[0] = fact[0] = factinv[0] = 1; for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i; factinv[n] = fact[n].inv(); inv[n] = fact[n - 1] * factinv[n]; for (int i = n - 1; i >= 1; i--) { factinv[i] = factinv[i + 1] * (i + 1); inv[i] = fact[i - 1] * factinv[i]; } } T C(int n, int r) { if (n < 0 || n < r || r < 0) return 0; return fact[n] * factinv[n - r] * factinv[r]; } T P(int n, int r) { if (n < 0 || n < r || r < 0) return 0; return fact[n] * factinv[n - r]; } T H(int n, int r) { if (n == 0 && r == 0) return 1; if (n < 0 || r < 0) return 0; return r == 0 ? 1 : C(n + r - 1, r); } }; template <class T> struct Matrix { int n; vector<vector<T>> m; Matrix() = default; Matrix(int x) : Matrix(vector<vector<T>>(x, vector<T>(x, 0))) {} Matrix(const vector<vector<T>> &a) { n = a.size(); m = a; } vector<T> &operator[](int i) { return m[i]; } const vector<T> &operator[](int i) const { return m[i]; } static Matrix identity(int x) { Matrix res(x); for (int i = 0; i < x; i++) res[i][i] = 1; return res; } Matrix operator+(const Matrix &a) const { Matrix x = (*this); return x += a; } Matrix operator*(const Matrix &a) const { Matrix x = (*this); return x *= a; } Matrix &operator+=(const Matrix &a) { Matrix res(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { res[i][j] = m[i][j] + a[i][j]; } } m = res.m; return *this; } Matrix &operator*=(const Matrix &a) { Matrix res(n); for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) { for (int j = 0; j < n; j++) { res[i][j] += m[i][k] * a[k][j]; } } } m = res.m; return *this; } Matrix pow(ll b) const { Matrix x = *this, res = identity(n); while (b) { if (b & 1) { res *= x; } x *= x; b >>= 1; } return res; } }; struct UnionFind { vector<int> par, siz, es; UnionFind(int x) { par.resize(x); siz.resize(x); es.resize(x); for (int i = 0; i < x; i++) { par[i] = i; siz[i] = 1; es[i] = 0; } } int find(int x) { if (par[x] == x) return x; return par[x] = find(par[x]); } bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) { es[x]++; return false; } if (siz[x] < siz[y]) swap(x, y); par[y] = x; siz[x] += siz[y]; es[x] += es[y] + 1; return true; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return siz[find(x)]; } int edges(int x) { return es[find(x)]; } }; template <class T, T (*op)(T, T), T (*e)()> struct disjointsparsetable { vector<vector<T>> table; vector<int> logtable; disjointsparsetable() = default; disjointsparsetable(vector<T> v) { int len = 0; while ((1 << len) <= v.size()) len++; table.assign(len, vector<T>(1 << len, e())); for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i]; for (int i = 1; i < len; i++) { int shift = 1 << i; for (int j = 0; j < (int)v.size(); j += shift << 1) { int t = min(j + shift, (int)v.size()); table[i][t - 1] = v[t - 1]; for (int k = t - 2; k >= j; k--) table[i][k] = op(v[k], table[i][k + 1]); if (v.size() <= t) break; table[i][t] = v[t]; int r = min(t + shift, (int)v.size()); for (int k = t + 1; k < r; k++) table[i][k] = op(table[i][k - 1], v[k]); } } logtable.resize(1 << len); for (int i = 2; i < logtable.size(); i++) { logtable[i] = logtable[(i >> 1)] + 1; } } T query(int l, int r) { if (l == r) return e(); if (l >= --r) return table[0][l]; int len = logtable[l ^ r]; return op(table[len][l], table[len][r]); }; }; pair<int, int> lcatree_op(pair<int, int> a, pair<int, int> b) { return min(a, b); } pair<int, int> lcatree_e() { return {1000000000, -1}; } struct lca_tree { int n, size; vector<int> in, ord, depth; disjointsparsetable<pair<int, int>, lcatree_op, lcatree_e> st; lca_tree(vector<vector<int>> g, int root = 0) : n((int)g.size()), size(log2(n) + 2), in(n), depth(n, n) { depth[root] = 0; function<void(int, int)> dfs = [&](int v, int p) { in[v] = (int)ord.size(); ord.push_back(v); for (int u : g[v]) { if (u == p) continue; if (depth[u] > depth[v] + 1) { depth[u] = depth[v] + 1; dfs(u, v); ord.push_back(v); } } }; dfs(root, -1); vector<pair<int, int>> vec((int)ord.size()); for (int i = 0; i < (int)ord.size(); i++) { vec[i] = make_pair(depth[ord[i]], ord[i]); } st = vec; } int lca(int u, int v) { if (in[u] > in[v]) swap(u, v); if (u == v) return u; return st.query(in[u], in[v]).second; } int dist(int u, int v) { int l = lca(u, v); return depth[u] + depth[v] - 2 * depth[l]; } }; struct auxiliary_tree : lca_tree { vector<vector<int>> G; auxiliary_tree(vector<vector<int>> &g) : lca_tree(g), G(n) {} pair<int, vector<int>> query(vector<int> vs, bool decending = false) { // decending:親から子の方向のみ辺を貼る assert(!vs.empty()); sort(vs.begin(), vs.end(), [&](int a, int b) { return in[a] < in[b]; }); int m = vs.size(); stack<int> st; st.push(vs[0]); for (int i = 0; i < m - 1; i++) { int w = lca(vs[i], vs[i + 1]); if (w != vs[i]) { int l = st.top(); st.pop(); while (!st.empty() && depth[w] < depth[st.top()]) { if (!decending) G[l].push_back(st.top()); G[st.top()].push_back(l); l = st.top(); st.pop(); } if (st.empty() || st.top() != w) { st.push(w); vs.push_back(w); } if (!decending) G[l].push_back(w); G[w].push_back(l); } st.push(vs[i + 1]); } while (st.size() > 1) { int x = st.top(); st.pop(); if (!decending) G[x].push_back(st.top()); G[st.top()].push_back(x); } // {root,vertex_list} return make_pair(st.top(), vs); } void clear(vector<int> vs) { for (int v : vs) G[v].clear(); } }; struct Mo { int n; vector<pair<int, int>> lr; explicit Mo(int n) : n(n) {} void add(int l, int r) { /* [l, r) */ lr.emplace_back(l, r); } template <typename AL, typename AR, typename EL, typename ER, typename O> void build(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out) { int q = (int)lr.size(); int bs = n / min<int>(n, sqrt(q)); vector<int> ord(q); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), [&](int a, int b) { int ablock = lr[a].first / bs, bblock = lr[b].first / bs; if (ablock != bblock) return ablock < bblock; return (ablock & 1) ? lr[a].second > lr[b].second : lr[a].second < lr[b].second; }); int l = 0, r = 0; for (auto idx : ord) { while (l > lr[idx].first) add_left(--l); while (r < lr[idx].second) add_right(r++); while (l < lr[idx].first) erase_left(l++); while (r > lr[idx].second) erase_right(--r); out(idx); } } template <typename A, typename E, typename O> void build(const A &add, const E &erase, const O &out) { build(add, add, erase, erase, out); } }; template <class S, S (*op)(S, S), S (*e)()> struct dual_segtree { int sz = 1, log = 0; vector<S> lz; dual_segtree() = default; dual_segtree(int n) : dual_segtree(vector<S>(n, e())) {} dual_segtree(vector<S> a) { int n = a.size(); while (sz < n) { sz <<= 1; log++; } lz.assign(sz << 1, e()); for (int i = 0; i < n; i++) lz[i + sz] = a[i]; } void push(int k) { int b = __builtin_ctz(k); for (int d = log; d > b; d--) { lz[k >> d << 1] = op(lz[k >> d << 1], lz[k >> d]); lz[k >> d << 1 | 1] = op(lz[k >> d << 1 | 1], lz[k >> d]); lz[k >> d] = e(); } } void apply(int l, int r, S x) { l += sz, r += sz; push(l); push(r); while (l < r) { if (l & 1) { lz[l] = op(lz[l], x); l++; } if (r & 1) { r--; lz[r] = op(lz[r], x); } l >>= 1, r >>= 1; } } S get(int k) { k += sz; S res = e(); while (k) { res = op(res, lz[k]); k >>= 1; } return res; } }; struct LowLink { vector<vector<int>> g; vector<int> ord, low, out; vector<bool> used; vector<pair<int, int>> bridge; vector<pair<int, int>> articulation; int unions; LowLink(vector<vector<int>> g) : g(g) { int n = (int)g.size(); ord.resize(n); low.resize(n); out.resize(n); used.resize(n); unions = 0; int t = 0; for (int i = 0; i < n; i++) { if (!used[i]) { dfs(i, t, -1); unions++; } } } void dfs(int v, int &t, int par) { used[v] = true; ord[v] = t++, low[v] = ord[v]; int cnt = 0; bool par_back = false; for (int to : g[v]) { if (!used[to]) { dfs(to, t, v); low[v] = min(low[v], low[to]); if (ord[v] < low[to]) bridge.push_back(minmax(v, to)); if (ord[v] <= low[to]) cnt++; } else if (to != par || par_back) { low[v] = min(low[v], ord[to]); } else par_back = true; } if (par != -1) cnt++; if (cnt >= 2) articulation.push_back({v, cnt}); out[v] = t; } }; namespace Geometry { constexpr double eps = 1e-10; template <class T, class U> constexpr bool equal(const T &a, const U &b) { return fabs(a - b) < eps; } template <class T> constexpr bool isZero(const T &a) { return fabs(a) < eps; } template <class T> constexpr T square(const T &a) { return a * a; } template <class T> struct Vec2 { T x, y; Vec2() = default; Vec2(T x, T y) : x(x), y(y) {}; constexpr Vec2 &operator+=(const Vec2 &P) const { x += P.x, y += P.y; return (*this); } constexpr Vec2 &operator-=(const Vec2 &P) const { x -= P.x, y -= P.y; return (*this); } constexpr Vec2 &operator*=(const T &k) const { x *= k, y *= k; return (*this); } constexpr Vec2 &operator/=(const T &k) const { x /= k, y /= k; return (*this); } constexpr Vec2 operator+() const { return *this; } constexpr Vec2 operator-() const { return {-x, -y}; } constexpr Vec2 operator+(const Vec2 &P) const { return {x + P.x, y + P.y}; } constexpr Vec2 operator-(const Vec2 &P) const { return {x - P.x, y - P.y}; } constexpr Vec2 operator*(const T &k) const { return {x * k, y * k}; } constexpr Vec2 operator/(const T &k) const { return {x / k, y / k}; } constexpr bool operator==(const Vec2 &P) const { return isZero(x - P.x) && isZero(y - P.y); } constexpr bool operator!=(const Vec2 &P) const { return !(*this == P); } constexpr bool operator<(const Vec2 &P) const { if (!isZero(x - P.x)) return x < P.x; return y < P.y; } constexpr bool operator>(const Vec2 &P) const { return P < *this; } constexpr bool isZeroVec() const { return x == T(0) && y == T(0); } constexpr T abs2() const { return x * x + y * y; } constexpr T abs() const { return sqrt(abs2()); } constexpr T dot(const Vec2 &v) const { return x * v.x + y * v.y; } constexpr T cross(const Vec2 &v) const { return x * v.y - y * v.x; } constexpr T dist(const Vec2 &P) const { return (P - (*this)).abs(); } constexpr T distSq(const Vec2 &P) const { return (P - (*this)).abs2(); } constexpr T unitVec() const { return (*this) / abs(); } Vec2 &unitize() { return *this /= abs(); } friend constexpr T abs2(const Vec2 &P) { return P.abs2(); } friend constexpr T abs(const Vec2 &P) { return P.abs(); } friend constexpr T dot(const Vec2 &P, const Vec2 &Q) { return P.dot(Q); } friend constexpr T dot(const Vec2 &A, const Vec2 &B, const Vec2 &C) { return (B - A).dot(C - A); } friend constexpr T cross(const Vec2 &P, const Vec2 &Q) { return P.cross(Q); } friend constexpr T cross(const Vec2 &A, const Vec2 &B, const Vec2 &C) { return (B - A).cross(C - A); } friend constexpr T dist(const Vec2 &P, const Vec2 &Q) { return abs(P - Q); } friend constexpr T distSq(const Vec2 &P, const Vec2 &Q) { return abs2(P - Q); } }; template <class T> constexpr int ccw(const Vec2<T> &A, const Vec2<T> &B, const Vec2<T> &C) { if (cross(B - A, C - A) > eps) return +1; if (cross(B - A, C - A) < -eps) return -1; if (dot(B - A, C - A) < -eps) return +2; if (abs2(B - A) + eps < abs2(C - A)) return -2; return 0; } struct Line { using T = long double; using Point = Vec2<T>; Point A, B; Line() = default; Line(Point A, Point B) : A(A), B(B) {} constexpr Point vec() const { return B - A; } constexpr bool isParallelTo(const Line &L) const { return isZero(cross(vec(), L.vec())); } constexpr bool isOrthogonalTo(const Line &L) const { return isZero(dot(vec(), L.vec())); } constexpr T distanceFrom(const Point &P) const { return abs(cross(P - A, vec())) / vec().abs(); } constexpr Point crosspoint(const Line &L) const { return A + vec() * (cross(A - L.A, L.vec())) / cross(L.vec(), vec()); } }; struct Segment : Line { Point A, B; Segment() = default; Segment(Point A, Point B) : Line(A, B) {} constexpr bool intersect(const Segment &L) const { return ccw(L.A, L.B, A) * ccw(L.A, L.B, B) <= 0 && ccw(A, B, L.A) * ccw(A, B, L.B) <= 0; } constexpr T distanceFrom(const Point &P) const { if (dot(P - A, vec()) < 0) return P.dist(A); if (dot(P - B, vec()) > 0) return P.dist(B); return Line::distanceFrom(P); } constexpr T distanceFrom(const Segment &L) const { if (intersect(L)) return 0; return min({Line::distanceFrom(L.A), Line::distanceFrom(L.B), Line(L).distanceFrom(A), Line(L).distanceFrom(B)}); } }; struct intLine { using T = long long; using Point = Vec2<T>; Point A, B; intLine() = default; intLine(Point A, Point B) : A(A), B(B) {} constexpr Point vec() const { return B - A; } constexpr bool isParallelTo(const intLine &L) const { return isZero(cross(vec(), L.vec())); } constexpr bool isOrthogonalTo(const intLine &L) const { return isZero(dot(vec(), L.vec())); } constexpr T distanceSqFrom(const Point &P) const { return square(cross(P - A, vec())) / vec().abs2(); } // constexpr Point crosspoint(const intLine &L) const { return A + vec() * (cross(A - L.A, L.vec())) / cross(L.vec(), vec()); } }; struct intSegment : intLine { intSegment() = default; intSegment(Point A, Point B) : intLine(A, B) {} constexpr bool intersect(const intSegment &L) { return ccw(L.A, L.B, A) * ccw(L.A, L.B, B) <= 0 && ccw(A, B, L.A) * ccw(A, B, L.B) <= 0; } constexpr T distanceSqFrom(const Point &P) { if (dot(P - A, vec()) < 0) return P.distSq(A); if (dot(P - B, vec()) > 0) return P.distSq(B); return intLine::distanceSqFrom(P); } constexpr T distanceSqFrom(const intSegment &L) { if (intersect(L)) return 0; return min({intLine::distanceSqFrom(L.A), intLine::distanceSqFrom(L.B), intLine(L).distanceSqFrom(A), intLine(L).distanceSqFrom(B)}); } }; template <class T> vector<T> convex_hull(vector<T> ps) { sort(ps.begin(), ps.end()); ps.erase(unique(ps.begin(), ps.end()), ps.end()); int n = ps.size(); if (n <= 2) return ps; vector<T> qs; for (auto &p : ps) { //<=0 if want to remove "3 points on a same line" while (qs.size() > 1 && cross(qs[qs.size() - 2], qs[qs.size() - 1], p) <= 0) { qs.pop_back(); } qs.push_back(p); } int t = qs.size(); for (int i = n - 2; i >= 0; i--) { T &p = ps[i]; while ((int)qs.size() > t && cross(qs[qs.size() - 2], qs[qs.size() - 1], p) <= 0) { qs.pop_back(); } if (i) qs.push_back(p); } return qs; } }; // namespace Geometry void solve() { int n, m; cin >> n >> m; using mint = modint<998244353>; cout << mint(-1).pow(n / m) * mint(10).pow(n % m) - 1 << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); int t; cin >> t; while (t--) solve(); }