#1177001 (C++17) No.3628 Sum of Superfibonacci Numbers

• 問題: No.3628 Sum of Superfibonacci Numbers
• ユーザー: 👑 Nachia
• 提出日時: 2026-08-14 22:44:44
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 230 ms / 2,000 ms
• コード長: 4,477 bytes
• コンパイル時間: 520 ms
• コンパイル使用メモリ: 105,544 KB
• 実行使用メモリ: 9,348 KB
• 最終ジャッジ日時: 2026-08-14 22:44:48
• 合計ジャッジ時間: 3,530 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 15

ソースコード

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

#include <utility>

#include <cassert>
namespace nachia{

// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const { return x; }
    my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; }
    bool operator==(const my_type& r) const { return x == r.x; }
    my_type pow(unsigned long long i) const {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const { return x; }
    int hval() const { return int(x > MOD/2 ? x - MOD : x); }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

} // namespace nachia
using Mint = nachia::StaticModint<998244353>;

struct Dp {
  Mint cnt[2][10][10][10] = {};

  Dp& operator+=(const Dp& r){
    REP(i,2) REP(j,10) REP(k,10) REP(l,10) cnt[i][j][k][l] += r.cnt[i][j][k][l];
    return *this;
  }

  Dp addDigit(ll l, ll r){
    Dp nx;
    REP(i,2) REP(a,10) REP(b,10) REP(c,10) for(ll d=l; d<=r; d++){
      nx.cnt[i | (b>c+d ? 1 : 0)][b][c][d] += cnt[i][a][b][c];
    }
    return nx;
  }

  void addSingleDigit(ll l, ll r){
    for(ll i=l; i<=r; i++) cnt[0][0][0][i] += 1;
  }
};

ll wt[1001] = {};

void testcase(){
  ll N; cin >> N; N += 1;
  REP(i,1000) wt[i] = INF;
  wt[1000] = 0;
  REP(a,10) REP(b,10) REP(c,10) if(a > b + c) wt[a * 100 + b * 10 + c] = 0;
  for(ll i=999; i>=0; i--) chmin(wt[i], wt[i+1] + 1);

  V<ll> digits; {
    ll n = N;
    while(n){
      digits.push_back(n % 10);
      n /= 10;
    }
  }

  Dp lt, ex;
  ex.addSingleDigit(digits.back(), digits.back());
  lt.addSingleDigit(1, digits.back()-1);
  digits.pop_back();

  while(digits.size()){
    ll d = digits.back(); digits.pop_back();
    lt = lt.addDigit(0, 9);
    lt += ex.addDigit(0, d-1);
    lt.addSingleDigit(1, 9);
    ex = ex.addDigit(d, d);
  }

//   REP(a,10){ REP(b,10){
//     REP(c,10){
//     cout << lt.cnt[0][a][b][c].val() << " ";
//   } cout << "  ";
// } cout << endl; } cout << endl;

  Mint ans = Mint(N) * Mint(N-1) / 2;
  REP(i,2) REP(a,10) REP(b,10) REP(c,10) if(i == 0) ans += lt.cnt[i][a][b][c] * wt[a*100 + b*10 + c];
  cout << ans.val() << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  ll T; cin >> T; REP(t,T)
  testcase();
  return 0;
}