結果
| 問題 | No.3566 Subsequence Sum |
| コンテスト | |
| ユーザー |
 pockyny
|
| 提出日時 | 2026-06-22 00:18:32 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 709 ms / 2,000 ms |
| コード長 | 8,753 bytes |
| 記録 | |
| コンパイル時間 | 1,549 ms |
| コンパイル使用メモリ | 175,612 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-06-22 00:18:43 |
| 合計ジャッジ時間 | 7,059 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 |
ソースコード
#include <iostream>
#include <atcoder/modint>
#include <vector>
#include <cassert>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
template<typename T = mint>
struct matrix {
int n,m;
vector<vector<T>> A;
matrix(vector<vector<T>> _A): A(_A){
n = A.size();
if(n){
m = A[0].size();
for(int i=1;i<n;i++) assert(A[i].size()==m);
}
}
matrix(int _n,int _m): n(_n), m(_m){
A.resize(n);
for(int i=0;i<n;i++) A[i].resize(m);
}
vector<T>& operator[](int row){return A[row];}
const vector<T>& operator[](int row) const { return A[row]; }
matrix operator+(const matrix& B) const {
assert(n == B.n && m == B.m);
matrix<T> C(n, m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
C[i][j] = A[i][j] + B[i][j];
}
}
return C;
}
matrix& operator+=(const matrix& B) {
assert(n == B.n && m == B.m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
A[i][j] += B[i][j];
}
}
return *this;
}
matrix operator-(const matrix& B) const {
assert(n == B.n && m == B.m);
matrix<T> C(n, m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
C[i][j] = A[i][j] - B[i][j];
}
}
return C;
}
matrix& operator-=(const matrix& B) {
assert(n == B.n && m == B.m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
A[i][j] -= B[i][j];
}
}
return *this;
}
matrix operator*(const matrix& B) const {
assert(m == B.n); // 列数と行数が一致すること
matrix<T> C(n, B.m);
for (int i = 0;i<n;i++) {
for (int j = 0;j<B.m;j++) {
for (int k = 0;k<m;k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
matrix& operator*=(const matrix& B) {
assert(m == B.n);
*this = *this * B;
return *this;
}
// 単位行列
matrix e(int n){
matrix ret(n,n);
for(int i=0;i<n;i++) ret[i][i] = 1;
return ret;
}
// Tr
matrix Tr(){
matrix ret(m,n);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++) ret[i][j] = A[j][i];
}
return ret;
}
// A^dを返す
// 破壊的にすることで高速化の余地あり
// verified: https://judge.yosupo.jp/submission/265168
matrix pw(long long d){
assert(n==m);
matrix ret = e(n);
matrix B = A;
while(d){
if(d&1) ret *= B;
B *= B; d /= 2;
}
return ret;
}
// 掃き出したもの (破壊的にして高速化の余地あり)
// 行列式でも使うので、isSwapで管理
// O(min(n,m)*nm)
// [掃き出し後の行列,[行列式を求めるときに-1をかけるか？,pivotになる列]] を返却
pair<matrix,pair<bool,vector<int>>> gaussian(){
matrix B = A;
bool isSwap = false;
// 今r行c列まで見た
// O(min(r,c)*r*c)
vector<int> pivots;
for(int r = 0,c = 0;r<n && c<m;){
int nx = -1;
for(int i=r;i<n;i++){
if(B[i][c].val()){
nx = i;
break;
}
}
if(nx==-1){
c++;
continue;
}
// 以下B[nx][c]!=0
// B[r][c]!=0にする
swap(B[r],B[nx]);
pivots.push_back(c);
if(nx!=r) isSwap ^= true;
for(int i2=0;i2<n;i2++){
if(B[i2][c]==0) continue;
if(i2==r){
T x = B[r][c];
for(int j=c;j<m;j++) B[i2][j] /= x;
}else{
T x = B[i2][c]/B[r][c];
for(int j=c;j<m;j++) B[i2][j] -= x*B[r][j];
}
}
r++; c++;
}
return {B,{isSwap,pivots}};
}
// verified: https://judge.yosupo.jp/submission/265176
T det(){
assert(n==m);
auto [B,f] = gaussian();
T ret = 1;
for(int i=0;i<n;i++) ret *= B[i][i];
if(f) ret *= -1;
return ret;
}
// O(min(n,m)nm)でrank計算
// 行列を複製するので高速化の余地あり
// verified: https://judge.yosupo.jp/submission/265180
// 多分転置しなくていい
int rank(){
matrix _A = n > m ? Tr() : A;
auto [B,_] = _A.gaussian();
// Traceを取っている可能性があることに注意
int ret = min(n,m);
for(int i=0;i<min(n,m);i++){
for(int j=0;j<max(n,m);j++){
if(B[i][j].val()) break;
if(j==max(n,m) - 1) ret--;
}
}
return ret;
}
//O(n^3)で逆行列を返す
//ないときは0*0行列を返す
// verify: https://judge.yosupo.jp/submission/265184
matrix inverse(){
assert(n==m);
matrix B(n,2*n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) B[i][j] = A[i][j];
B[i][n + i] = 1;
}
auto [C,_] = B.gaussian();
for(int i=0;i<n;i++){
if(C[i][i]==0) return matrix(0,0);
for(int j=0;j<i;j++){
mint x = C[j][i]/C[i][i];
for(int k=i;k<2*n;k++){
C[j][k] -= C[i][k]*x;
}
}
mint x = C[i][i];
for(int j=i;j<2*n;j++){
C[i][j] /= x;
}
}
matrix ret(n,n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) ret[i][j] = C[i][j + n];
}
return ret;
}
// O((n + m)*n*m)でkerを求める
// 掃きだしはO(min(n,m)*n*m)でできるが、kerはm次元vectorがmax(n,m) - rank(A)なので、
// kerの基底の行列のサイズがO((n + m)*m)くらいにはなりうる
// verifyは出来ていない (これ https://atcoder.jp/contests/utpc2024/tasks/utpc2024_n でしたかったが、計算量的にTLEする)
matrix kernel() {
assert(n != 0); // 空の行列に対してカーネルは無意味
auto [B,_] = gaussian();
auto [__,pivots] = _;
// 基底ベクトルを求める
vector<vector<mint>> basis;
vector<bool> is_pivot(m, false);
for (int p : pivots) is_pivot[p] = true;
for (int c = 0; c < m; ++c) {
if (!is_pivot[c]) {
// pivotではない列について1をたてて、掃き出し後の行列で0でない行については、
// pivot (掃き出し後で1になっている) で調整するイメージ
vector<mint> vec(m, 0);
vec[c] = 1;
for (int i = 0; i < pivots.size(); ++i) {
vec[pivots[i]] = -B[i][c];
}
basis.push_back(vec);
}
}
return matrix(basis);
}
};
#include <iostream>
#include <string>
#include <vector>
#include <atcoder/modint>
#include <array>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
typedef long long ll;
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
string s; cin >> s;
ll k; cin >> k;
int i,j,l,n = s.size();
// 先頭10個 := 末尾がiの総和
// 後半10個 := 末尾がiの個数
// 20変数の線形和をもって計算する
const int SZ = 20;
array<array<mint,20>,20> v;
for(i=0;i<SZ;i++) v[i][i] = 1;
array<mint,SZ> ar_v,ar_c;
for(i=0;i<n;i++){
for(j=0;j<SZ;j++) ar_v[j] = 0, ar_c[j] = 0;
for(j=0;j<10;j++){
for(l=0;l<SZ;l++){
ar_v[l] += v[j][l]*10 + v[10 + j][l]*(s[i] - '0');
ar_c[l] += v[10 + j][l];
}
}
for(j=0;j<SZ;j++){
v[s[i] - '0'][j] = ar_v[j];
v[s[i] - '0' + 10][j] = ar_c[j];
}
}
matrix<mint> A(SZ,SZ);
for(i=0;i<SZ;i++){
for(j=0;j<SZ;j++) A[i][j] = v[i][j];
}
matrix<mint> B = A.pw(k);
matrix<mint> C(SZ,1);
// 先頭0の文字だけ持ってるという解釈
C[10][0] = 1;
matrix<mint> D = B*C;
mint ans = 0;
for(i=0;i<10;i++) ans += D[i][0];
cout << ans.val() << "\n";
// for(i=10;i<SZ;i++){
// for(j=10;j<SZ;j++){
// cout << A[i][j].val() << " ";
// }
// cout << "\n";
// }
}