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

• 問題: No.3566 Subsequence Sum
• ユーザー: Kude
• 提出日時: 2026-06-06 00:04:11
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 267 ms / 2,000 ms
• コード長: 3,639 bytes
• コンパイル時間: 2,656 ms
• コンパイル使用メモリ: 363,720 KB
• 実行使用メモリ: 20,096 KB
• 最終ジャッジ日時: 2026-06-06 00:04:16
• 合計ジャッジ時間: 4,789 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using mint = modint998244353;



template<class T, T (*add)(T, T), T (*zero)(), T (*mul)(T, T), T (*one)(), int N>
struct Mat : array<array<T, N>, N> {
  using M = Mat<T, add, zero, mul, one, N>;
  void make_identity() {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        (*this)[i][j] = zero();
      }
    }
    for (int i = 0; i < N; i++) {
      (*this)[i][i] = one();
    }
  }
  M& operator+=(const M& rhs) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        (*this)[i][j] = add((*this)[i][j], rhs[i][j]);
      }
    }
    return *this;
  }
  M& operator*=(const M& rhs) {
    static M temp;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        temp[i][j] = zero();
      }
    }
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
          temp[i][k] = add(temp[i][k], mul((*this)[i][j], rhs[j][k]));
        }
      }
    }
    *this = temp;
    return *this;
  }
  template <class I>
  void inplace_pow(I k) {
    assert(k >= 0);
    static M temp;
    temp = *this;
    make_identity();
    while (k) {
      if (k & 1) *this *= temp;
      k >>= 1;
      if (k) temp *= temp;
    }
  }
  friend ostream& operator<<(ostream& os, const M& A) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        os << A[i][j] << " \n"[j + 1 == N];
      }
    }
    return os;
  }
};


// mint
mint add0(mint x, mint y) { return x + y; }
mint zero0() { return mint(); }
mint mul0(mint x, mint y) { return x * y; }
mint one0() { return mint::raw(1); }
using M0 = Mat<mint, add0, zero0, mul0, one0, 2>;

M0 add(M0 x, M0 y) { x += y; return x; }
M0 zero() { return M0{}; }
M0 mul(M0 x, M0 y) { x *= y; return x; }
M0 one() { M0 z; z.make_identity(); return z; }

using M = Mat<M0, add, zero, mul, one, 11>;

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  int k;
  cin >> s >> k;
  int n = s.size();
  M m;
  rep(u, 10) {
    int i = 0;
    while (i < n && s[i] - '0' != u) i++;
    if (i == n) {
      m[u][u] = one();
      continue;
    }
    int last[10]{};
    last[u] = i;
    static vector<M0> acc;
    acc.assign(n + 1, M0{});
    acc[i+1][0][0] = 1;
    acc[i+1][0][1] = u;
    acc[i+1][1][0] = 0;
    acc[i+1][1][1] = 10;
    for (i++; i < n; i++) {
      int x = s[i] - '0';
      M0 t = acc[i];
      rep(i, 2) rep(j, 2) t[i][j] -= acc[last[x]][i][j];
      M0 tt;
      tt[0][0] = 1;
      tt[0][1] = x;
      tt[1][0] = 0;
      tt[1][1] = 10;
      t *= tt;
      acc[i+1] = acc[i];
      acc[i+1] += t;
      last[x] = i;
    }
    rep(v, 10) {
      M0 t = acc[n];
      rep(i, 2) rep(j, 2) t[i][j] -= acc[last[v]][i][j];
      m[u][v] = t;
    }
    m[u][10] += acc[n];
  }
  m[10][10].make_identity();
  m.inplace_pow(k);
  mint ans;
  rep(u, 10) if (u) ans += m[u][10][0][1];
  cout << ans.val() << '\n';
}