#1001571 (C++17) No.2699 Simple Math (Returned)

提出ソース
結果

問題	No.2699 Simple Math (Returned)
ユーザー	anmichi
提出日時	2024-08-11 20:37:56
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	380 ms / 2,000 ms
コード長	21,313 bytes
コンパイル時間	2,250 ms
コンパイル使用メモリ	214,848 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-08-11 20:38:04
合計ジャッジ時間	7,642 ms
ジャッジサーバーID （参考情報）	judge2 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	271 ms 5,376 KB
testcase_02	AC	312 ms 5,376 KB
testcase_03	AC	268 ms 5,376 KB
testcase_04	AC	355 ms 5,376 KB
testcase_05	AC	309 ms 5,376 KB
testcase_06	AC	299 ms 5,376 KB
testcase_07	AC	327 ms 5,376 KB
testcase_08	AC	326 ms 5,376 KB
testcase_09	AC	319 ms 5,376 KB
testcase_10	AC	369 ms 5,376 KB
testcase_11	AC	380 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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>;
    if ((n / m) % 2 == 0) {
        cout << mint(10).pow(n % m) - 1 << endl;
    } else {
        cout << mint(10).pow(m) - mint(10).pow(n % m) << endl;
    }
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) solve();
}
yukicoder

結果

テストケース

ソースコード
