結果

問題 No.3277 Forever Monotonic Number
ユーザー areik
提出日時 2025-09-19 22:51:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,867 bytes
コンパイル時間 3,954 ms
コンパイル使用メモリ 262,600 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-19 22:52:12
合計ジャッジ時間 17,634 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using isize = size_t;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using f64 = long double;
using p2 = pair<i64, i64>;
using el = tuple<i64, i64, i64>;
using mint = atcoder::modint998244353;

void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
  _main();
}

i64 pow(i64 x, i64 n) {
  i64 res = 1;
  i64 t = x;
  while (n > 0) {
    if (n & 1) res *= t;
    t *= t;
    n >>= 1;
  }
  return res;
}
i64 pow(i64 x, i64 n, i64 m) {
  i64 res = 1;
  i64 t = x % m;
  while (n > 0) {
    if (n & 1) res = res * t % m;
    t = t * t % m;
    n >>= 1;
  }
  return res;
}

void _main() {
  vector<i64> v;
  vector<bool> monotonic(20000, true);
  for (i64 i = 1; i <= monotonic.size(); i++) {
    string s = to_string(i);
    i64 sum = 0;
    for (i64 j = 1; j < s.size(); j++) monotonic[i] = monotonic[i] && s[j - 1] <= s[j];
    for (i64 j = 0; j < s.size(); j++) sum += s[j] - '0';
    monotonic[i] = monotonic[i] && monotonic[sum];
    if (s.size() == 1 || monotonic[i]) {
      v.push_back(i);
    }
  }
  i64 ttt;
  cin >> ttt;
  for (;ttt--;) {
    i64 n;
    cin >> n;
    if (n == 0) {
      cout << "1\n";
      continue;
    }
    i64 ans = 1e18;
    {
      i64 len = to_string(n + 1).size() + 1;
      i64 x = v[lower_bound(v.begin(), v.end(), len) - v.begin()];
      i64 res = 0;
      for (i64 i = len; true; i++) {
        if (x > 9 * i) continue;
        x -= i;
        i64 c = 0;
        while (x >= 8) x -= 8, c++;
        res = pow(10, c) - 1;
        if (x > 0) {
          res += pow(10, c) * (x + 1);
        }
        res += (pow(10, i) - 1) / 9;
        break;
      }
      ans = min(ans, res);
    }
    {
      string S = to_string(n + 1);
      i64 len = S.size();
      vector<vector<i64>> dp(10, vector<i64>(9*len + 1, 1e18));
      i64 mx = 0;
      for (i64 i = 0; i < len; i++) {
        vector<vector<i64>> ndp(10, vector<i64>(9*len + 1, 1e18));
        for (i64 j = 0; j < 10; j++) {
          for (i64 s = 0; s <= 9*len; s++) {
            if (dp[j][s] == 1e18) continue;
            for (i64 k = j; k < 10 && s + k < dp.size(); k++) {
              ndp[k][s + k] = min(ndp[k][s + k], dp[j][s] * 10 + k);
            }
          }
        }
        swap(dp, ndp);
        i64 s = 0;
        i64 now = 0;
        bool ok = true;
        for (i64 j = 0; j < i; j++) s += S[j] - '0';
        for (i64 j = 0; j < i; j++) now = now * 10 + S[j] - '0';
        for (i64 j = 1; j < i; j++) ok &= S[j - 1] <= S[j];
        if (ok) {
          for (i64 j = max(mx, i64(S[i] - '0' + 1)); j < 10; j++) {
            dp[j][s + j] = min(dp[j][s + j], now * 10 + j);
          }
        }
        mx = max(mx, i64(S[i] - '0'));
      }
      {
        bool ok = true;
        for (i64 j = 1; j < S.size(); j++) ok &= S[j - 1] <= S[j];
        i64 sum = 0;
        for (i64 j = 0; j < S.size(); j++) sum += S[j] - '0';
        if (ok) dp[0][sum] = min(dp[0][sum], n + 1);
      }
      for (i64 i = 0; i <= 9*len; i++) {
        i64 mn = 1e18;
        for (i64 j = 0; j < 10; j++) {
          mn = min(mn, dp[j][i]);
        }
        if (mn == 1e18) continue;
        if (monotonic[i]) {
          ans = min(ans, mn);
        }
      }
    }
    // ans <= i * 9;
    // ans / 9 <= i
    for (i64 i = max(n + 1, ans / 9); true; i++) {
      if (ans > i * 9) continue;
      mint cur = 0;
      if (ans == i * 9) {
        cur = mint(10).pow(i) - 1;
      } else {
        cur += (mint(10).pow(i) - 1) / 9;
        ans -= i;
        i64 c = ans / 8;
        cur += (mint(10).pow(c) - 1) / 9 * 8;
        ans -= c * 8;
        cur += mint(10).pow(c) * ans;
      }
      cout << cur.val() << "\n";
      break;
    }
  }
}
0