結果

問題 No.3089 Base M Numbers, But Only 0~9
ユーザー nonon
提出日時 2025-04-04 22:31:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,297 bytes
コンパイル時間 4,823 ms
コンパイル使用メモリ 277,720 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2025-04-04 22:32:11
合計ジャッジ時間 5,366 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 13 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<int MOD>
struct modint {
    modint() : x(0) {}
    modint(long long v) {
        long long y = v % m();
        if (y < 0) y += m();
        x = (unsigned int)(y);
    }
    static modint raw(int v) {
        modint a;
        a.x = v;
        return a;
    }
    static constexpr int mod() { return m(); }
    unsigned int val() const { return x; }
    modint& operator++() {
        x++;
        if (x == m()) x = 0;
        return *this;
    }
    modint& operator--() {
        if (x == 0) x = m();
        x--;
        return *this;
    }
    modint operator++(int) {
        modint res = *this;
        ++*this;
        return res;
    }
    modint operator--(int) {
        modint res = *this;
        --*this;
        return res;
    }
    modint& operator+=(const modint &r) {
        x += r.x;
        if (x >= m()) x -= m();
        return *this;
    }
    modint& operator-=(const modint &r) {
        x -= r.x;
        if (x >= m()) x += m();
        return *this;
    }
    modint& operator*=(const modint &r) {
        unsigned long long y = x;
        y *= r.x;
        x = (unsigned int)(y % m());
        return *this;
    }
    modint &operator/=(const modint &r) {
        return *this = *this * r.inv();
    }
    friend modint operator+(const modint &a, const modint &b) {
        return modint(a) += b;
    }
    friend modint operator-(const modint &a, const modint &b) {
        return modint(a) -= b;
    }
    friend modint operator*(const modint &a, const modint &b) {
        return modint(a) *= b;
    }
    friend modint operator/(const modint &a, const modint &b) {
        return modint(a) /= b;
    }
    friend bool operator==(const modint &a, const modint &b) {
        return a.x == b.x;
    }
    friend bool operator!=(const modint &a, const modint &b) {
        return a.x != b.x;
    }
    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }
    modint pow(long long k) const {
        assert(k >= 0);
        modint a = *this;
        modint res = 1;
        while (k > 0) {
            if (k & 1) res *= a;
            a *= a;
            k >>= 1;
        }
        return res;
    }
    modint inv() const {
        long long a = x, b = m(), u = 1, v = 0;
        while (b > 0) {
            long long t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return modint(u);
    }
private:
    unsigned int x;
    static constexpr unsigned int m() { return MOD; }
};

using mint = modint<998244353>;

pair<mint, mint> f(mint a, mint b) {
    mint n = (b - a) / 10 + 1;
    return {n, n * (a + b) / 2};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long M;
    string N;
    cin >> M >> N;
    vector<mint> C(10), X(10);
    for (int j = 0; j < 10; j++) {
        auto m = max(0LL, M - 15);
        while (m % 10 != j) m++;
        while (m + 10 < M) m += 10;
        auto [c, x] = f(j, m);
        C[j] = c;
        X[j] = x;
    }
    mint t = 1;
    for (auto d : N) t *= C[d - '0'];
    mint ans = 0;
    for (auto d : N) {
        int i = d - '0';
        ans *= M;
        ans += X[i] * (t / C[i]);
    }
    cout << ans.val() << endl;
}
0