結果
| 問題 | No.2699 Simple Math (Returned) |
| ユーザー |
 anmichi
|
| 提出日時 | 2024-08-11 20:37:56 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 11 |
ソースコード
#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();
}