結果
| 問題 | No.3277 Forever Monotonic Number | 
| コンテスト | |
| ユーザー |  tnakao0123 | 
| 提出日時 | 2025-09-20 17:23:25 | 
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) | 
| 結果 | 
                                AC
                                 
                             | 
| 実行時間 | 168 ms / 4,000 ms | 
| コード長 | 2,856 bytes | 
| コンパイル時間 | 421 ms | 
| コンパイル使用メモリ | 61,220 KB | 
| 実行使用メモリ | 8,524 KB | 
| 最終ジャッジ日時 | 2025-09-20 17:23:28 | 
| 合計ジャッジ時間 | 2,789 ms | 
| ジャッジサーバーID (参考情報) | judge1 / judge3 | 
(要ログイン)
| ファイルパターン | 結果 | 
|---|---|
| sample | AC * 1 | 
| other | AC * 9 | 
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:95:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   95 |   scanf("%d", &tn);
      |   ~~~~~^~~~~~~~~~~
main.cpp:99:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   99 |     scanf("%lld", &n);
      |     ~~~~~^~~~~~~~~~~~
            
            ソースコード
/* -*- coding: utf-8 -*-
 *
 * 3277.cc:  No.3277 Forever Monotonic Number - yukicoder
 */
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
/* constant */
const int MAX_L = 15;
const int MOD = 998244353;
/* typedef */
using ll = long long;
using vl = vector<ll>;
template<const int MOD>
struct MI {
  int v;
  MI(): v() {}
  MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; }
  MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; }
  explicit operator int() const { return v; }
  
  MI operator+(const MI m) const { return MI(v + m.v); }
  MI operator-(const MI m) const { return MI(v + MOD - m.v); }
  MI operator-() const { return MI(MOD - v); }
  MI operator*(const MI m) const { return MI((long long)v * m.v); }
  MI &operator+=(const MI m) { return (*this = *this + m); }
  MI &operator-=(const MI m) { return (*this = *this - m); }
  MI &operator*=(const MI m) { return (*this = *this * m); }
  bool operator==(const MI m) const { return v == m.v; }
  bool operator!=(const MI m) const { return v != m.v; }
  MI pow(long long n) const {  // a^n % MOD
    MI pm = 1, a = *this;
    while (n > 0) {
      if (n & 1) pm *= a;
      a *= a;
      n >>= 1;
    }
    return pm;
  }
  MI inv() const { return pow(MOD - 2); }
  MI operator/(const MI m) const { return *this * m.inv(); }
  MI &operator/=(const MI m) { return (*this = *this / m); }
};
using mi = MI<MOD>;
/* global variables */
ll ts[MAX_L + 1];
vl fms;
mi inv9 = mi(9).inv();
/* subroutines */
void rec(int l, int d, ll s) {
  if (l <= 0) {
    int dsum = 0;
    for (ll m = s; m > 0; m /= 10) dsum += m % 10;
    auto vit = lower_bound(fms.begin(), fms.end(), (ll)dsum);
    if (vit != fms.end() && *vit == dsum) fms.push_back(s);
    return;
  }
  if (d >= 10) return;
  for (int i = l; i >= 0; i--)
    rec(l - i, d + 1, s * ts[i] + (ts[i] - 1) / 9 * d);
}
/* main */
int main() {
  ts[0] = 1;
  for (int i = 0; i < MAX_L; i++) ts[i + 1] = ts[i] * 10;
  
  for (int i = 1; i <= 9; i++) fms.push_back(i);
  for (int l = 2; l <= MAX_L; l++) rec(l, 1, 0);
  //printf(" fms=%d\n", (int)fms.size());
  //for (auto f: fms) printf(" %lld", f); putchar('\n');
  
  int tn;
  scanf("%d", &tn);
  while (tn--) {
    ll n;
    scanf("%lld", &n);
    if (n == 0) { puts("1"); continue; }
    n++;
    //printf("n=%lld\n", n);
    auto vit = lower_bound(fms.begin(), fms.end(), n);
    //printf(" f=%lld\n", *vit);
    ll s0 = *vit - n;
    ll c9 = s0 / 8;
    int r = s0 % 8;
    ll c1 = n - (c9 + 1);
    //printf(" c1=%lld,r=%d,c9=%lld\n", c1, r, c9);
    mi tc9 = mi(10).pow(c9), tc1 = mi(10).pow(c1), tn = mi(10).pow(n);
    //mi sum = (tc1 - 1) * inv9;
    //sum = sum * 10 + (r + 1);
    //sum = sum * tc9 + (tc9 - 1) * inv9 * 9;
    mi sum = (tn - 1) * inv9 + tc9 * r + (tc9 - 1) * inv9 * 8;
    printf("%d\n", (int)sum);
  }
  return 0;
}
            
            
            
        