結果

問題 No.3277 Forever Monotonic Number
コンテスト
ユーザー ripity
提出日時 2025-09-19 23:28:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,308 ms / 4,000 ms
コード長 2,096 bytes
コンパイル時間 3,133 ms
コンパイル使用メモリ 283,496 KB
実行使用メモリ 9,064 KB
最終ジャッジ日時 2025-09-19 23:28:33
合計ジャッジ時間 10,111 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long;

bool chmin(auto &a, auto b) { return a > b ? a = b, true : false; }
bool chmax(auto &a, auto b) { return a < b ? a = b, true : false; }

#include <atcoder/modint>
using mint = atcoder::modint998244353;

ll digit_sum(ll x) {
    ll ret = 0;
    while(x) {
        ret += x % 10;
        x /= 10;
    }
    return ret;
}

bool is_monotonic(ll x) {
    int p = 10, q;
    while(x) {
        q = x % 10;
        if(p < q) return false;
        x /= 10;
        swap(p, q);
    }
    return true;
}

bool is_forever_monotonic(ll x) {
    while(x >= 10) {
        if(!is_monotonic(x)) return false;
        x = digit_sum(x);
    }
    return true;
}

vector<ll> A;
void precalc() {
    vector<int> v;
    for(int i = 0; i < 15; i++) v.push_back(0);
    for(int i = 0; i <  9; i++) v.push_back(1);
    do {
        ll x = 0, s = 0;
        for(int f : v) {
            if(f) s += 1;
            else x = 10 * x + s;
        }
        if(is_forever_monotonic(x)) A.push_back(x);
    }while(next_permutation(v.begin(), v.end()));
}

mint repunit(ll len) {
    if(len == 0) {
        return 0;
    }else if(len % 2 == 1) {
        return 1 + 10 * repunit(len - 1);
    }else {
        mint r = repunit(len / 2);
        return r + mint(10).pow(len / 2) * r;
    }
}

void sol(ll N) {
    ll L = *lower_bound(A.begin(), A.end(), N + 1) - (N + 1);
    ll m = L / 8, r = L % 8;
    mint ans;
    // cout << repunit(1).val() << endl;
    // cout << L << " " << m << " " << r << endl;
    ans += repunit(N + 1);
    ans += 8 * repunit(m);
    ans += r * mint(10).pow(m);
    cout << ans.val() << endl;
}

void solve() {
    ll N;
    cin >> N;
    ll n = N;
    for(;; n++) {
        ll L = *lower_bound(A.begin(), A.end(), n + 1) - (n + 1);
        if(8 * (n + 1) >= L) { sol(n); break; }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    precalc();
    // cout << A.size() << endl;
    // sort(A.begin(), A.end());
    // for(ll a : A) cout << a << "\n";

    int T;
    cin >> T;
    while(T--) solve();
}
0