#1168338 (C++23) No.3566 Subsequence Sum

• 問題: No.3566 Subsequence Sum
• ユーザー: t98slider
• 提出日時: 2026-06-05 22:20:37
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,310 bytes
• コンパイル時間: 5,354 ms
• コンパイル使用メモリ: 377,932 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-06-05 22:21:09
• 合計ジャッジ時間: 8,218 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 7 TLE * 1 -- * 7

ソースコード

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

template <class T, size_t N> struct Matrix {
    std::array<std::array<T, N>, N> A{};
    Matrix() {}
    Matrix(const std::array<std::array<T, N>, N> &M) : A(M){}
    Matrix(const std::vector<std::vector<T>> &M)  {
        for(size_t i = 0; i < N; i++){
            for(size_t j = 0; j < N; j++){
                A[i][j] = M[i][j];
            }
        }
    }
    const std::array<T, N>& operator[](int i) const { return A[i]; }
    std::array<T, N>& operator[](int i) { return A[i]; }

    Matrix& operator+=(const Matrix& rhs) {
        for(size_t i = 0; i < N; i++){
            for(size_t j = 0; j < N; j++){
                A[i][j] += rhs[i][j];
            }
        }
        return *this;
    }
    Matrix& operator-=(const Matrix& rhs) {
        for(size_t i = 0; i < N; i++){
            for(size_t j = 0; j < N; j++){
                A[i][j] -= rhs[i][j];
            }
        }
        return *this;
    }
    Matrix& operator*=(const Matrix& rhs) {
        std::array<std::array<T, N>, N> res{};
        for(size_t i = 0; i < N; i++){
            for(size_t j = 0; j < N; j++){
                for(size_t k = 0; k < N; k++){
                    res[i][j] += A[i][k] * rhs[k][j];
                }
            }
        }
        swap(A, res);
        return *this;
    }
    Matrix& operator+() const { return *this; }
    Matrix& operator-() const { return Matrix() - *this; }
    friend Matrix operator+(const Matrix& lhs, const Matrix& rhs) {
        return Matrix(lhs) += rhs;
    }
    friend Matrix operator-(const Matrix& lhs, const Matrix& rhs) {
        return Matrix(lhs) -= rhs;
    }
    friend Matrix operator*(const Matrix& lhs, const Matrix& rhs) {
        return Matrix(lhs) *= rhs;
    }
    friend bool operator==(const Matrix& lhs, const Matrix& rhs) {
        return (lhs.A == rhs.A);
    }
    friend bool operator!=(const Matrix& lhs, const Matrix& rhs) {
        return (lhs.A != rhs.A);
    }
    Matrix pow(long long v){
        Matrix res, temp = A;
        for(size_t i = 0; i < N; i++)res[i][i] = 1;
        while(v){
            if(v & 1)res *= temp;
            temp *= temp;
            v >>= 1;
        }
        return res;
    }
    friend std::ostream& operator << (std::ostream &os, const Matrix& rhs) noexcept {
        for(size_t i = 0; i < N; i++){
            if(i) os << '\n';
            for(size_t j = 0; j < N; j++){
                os << (j ? " " : "") << rhs[i][j];
            }
        }
        return os;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;
    string s;
    cin >> s >> k;
    vector<Matrix<mint, 20>> Mt(10);
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 20; j++) Mt[i][j][j] = 1;
        for(int j = 0; j < 10; j++){
            Mt[i][j][i] = 1;
            Mt[i][j][10 + i] = i;
            Mt[i][10 + j][10 + i] = 10;
        }
    }
    auto B = Mt[s[0] - '0'];
    for(int i = 1; i < (int)s.size(); ){
        int p = i;
        while(i < (int)s.size() && s[i] == s[p]) i++;
        B *= Mt[s[p] - '0'].pow(i - p);
    }
    auto res = B.pow(k);
    mint ans = 0;
    for(int i = 0; i < 10; i++){
        ans += res[0][10 + i];
    }
    cout << ans.val() << '\n';
}