#1170671 (C++23(gcc16)) No.3628 Sum of Superfibonacci Numbers

• 問題: No.3628 Sum of Superfibonacci Numbers
• ユーザー: 👑 loop0919
• 提出日時: 2026-07-10 00:46:07
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 6 ms / 2,000 ms
• コード長: 5,395 bytes
• コンパイル時間: 4,375 ms
• コンパイル使用メモリ: 358,396 KB
• 実行使用メモリ: 9,344 KB
• 最終ジャッジ日時: 2026-08-14 20:52:02
• 合計ジャッジ時間: 3,919 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

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

ソースコード

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

using int64 = long long;

const int64 MOD = 998244353;
const int64 INV2 = (MOD + 1) / 2;

int fullCost[10][10];
int partCost[10][10][100];

bool is_good(long long n) {
    vector<int> d;

    while (n > 0) {
        d.push_back(n % 10);
        n /= 10;
    }

    for (int i = 0; i + 2 < (int)d.size(); i++) {
        if (d[i + 2] > d[i + 1] + d[i]) {
            return true;
        }
    }

    return false;
}

void build_cost() {
    for (int u = 0; u < 10; u++) {
        for (int v = 0; v < 10; v++) {
            bool good[101] = {};

            for (int r = 0; r < 100; r++) {
                int a = r % 10;
                int b = r / 10;

                good[r] = (u > a + b) || (v > u + b);
            }

            // 次のブロックの先頭 100(q+1) は必ず良い数
            good[100] = true;

            int dist[100];
            int nxt = 100;

            for (int r = 99; r >= 0; r--) {
                if (good[r]) nxt = r;
                dist[r] = nxt - r;
            }

            int sum = 0;
            int pref = 0;

            for (int r = 0; r < 100; r++) {
                sum += dist[r];
                pref += dist[r];
                partCost[u][v][r] = pref;
            }

            fullCost[u][v] = sum;
        }
    }
}

// cnt[u][v] =
// 1 <= q <= X のうち、
// q が良い数でなく、
// q の一の位が u、十の位が v であるものの個数
array<array<long long, 10>, 10> count_bad_by_last2(long long X) {
    array<array<long long, 10>, 10> cnt{};
    for (auto &row : cnt) row.fill(0);

    if (X <= 0) return cnt;

    string s = to_string(X);

    static long long dp[11][11][2][2];
    static long long ndp[11][11][2][2];

    memset(dp, 0, sizeof(dp));

    // p2, p1, started, tight
    // p2, p1 は直近 2 桁
    // 10 は「まだ存在しない」ことを表す
    dp[10][10][0][1] = 1;

    for (char ch : s) {
        memset(ndp, 0, sizeof(ndp));

        for (int p2 = 0; p2 <= 10; p2++) {
            for (int p1 = 0; p1 <= 10; p1++) {
                for (int started = 0; started <= 1; started++) {
                    for (int tight = 0; tight <= 1; tight++) {
                        long long ways = dp[p2][p1][started][tight];
                        if (ways == 0) continue;

                        int lim = tight ? ch - '0' : 9;

                        for (int dig = 0; dig <= lim; dig++) {
                            int ntight = tight && (dig == lim);

                            if (!started && dig == 0) {
                                ndp[10][10][0][ntight] += ways;
                                continue;
                            }

                            if (!started) {
                                // 最初の非ゼロ桁
                                ndp[10][dig][1][ntight] += ways;
                            } else if (p2 == 10) {
                                // 2 桁目
                                ndp[p1][dig][1][ntight] += ways;
                            } else {
                                // p2, p1, dig の 3 桁が良い条件を満たさない場合だけ遷移
                                if (p2 <= p1 + dig) {
                                    ndp[p1][dig][1][ntight] += ways;
                                }
                            }
                        }
                    }
                }
            }
        }

        memcpy(dp, ndp, sizeof(dp));
    }

    for (int p2 = 0; p2 <= 10; p2++) {
        for (int p1 = 0; p1 <= 10; p1++) {
            for (int tight = 0; tight <= 1; tight++) {
                long long ways = dp[p2][p1][1][tight];
                if (ways == 0) continue;

                if (p2 == 10) {
                    // 1 桁の数の場合、十の位は 0
                    cnt[p1][0] += ways;
                } else {
                    // 一の位が p1、十の位が p2
                    cnt[p1][p2] += ways;
                }
            }
        }
    }

    return cnt;
}

long long distance_sum_mod(long long N) {
    long long Q = N / 100;
    int R = (int)(N % 100);

    long long ans = 0;

    if (Q == 0) {
        // 1..N はすべて良い数でない
        // f(k) = 100
        for (int r = 1; r <= R; r++) {
            ans += 100 - r;
        }
        return ans % MOD;
    }

    // q = 0 のブロック、つまり 1..99
    // f(k) = 100 なので距離総和は 99 + 98 + ... + 1 = 4950
    ans = 4950;

    // 完全に含まれるブロック q = 1..Q-1
    auto cnt = count_bad_by_last2(Q - 1);

    for (int u = 0; u < 10; u++) {
        for (int v = 0; v < 10; v++) {
            ans += (cnt[u][v] % MOD) * 1LL * fullCost[u][v] % MOD;
            ans %= MOD;
        }
    }

    // 最後のブロック q = Q, r = 0..R
    if (!is_good(Q)) {
        int u = Q % 10;
        int v = (Q / 10) % 10;

        ans += partCost[u][v][R];
        ans %= MOD;
    }

    return ans;
}

long long solve(long long N) {
    long long base = (N % MOD) * ((N + 1) % MOD) % MOD * INV2 % MOD;
    long long dist = distance_sum_mod(N);

    return (base + dist) % MOD;
}

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

    build_cost();

    int T;
    cin >> T;

    while (T--) {
        long long N;
        cin >> N;
        cout << solve(N) << '\n';
    }

    return 0;
}