結果

問題 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);
      |     ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

/* -*- 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;
}
0