結果
問題 |
No.3304 INCREASE decrease
|
ユーザー |
|
提出日時 | 2025-10-05 16:33:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 258 ms / 2,000 ms |
コード長 | 24,102 bytes |
コンパイル時間 | 5,769 ms |
コンパイル使用メモリ | 310,608 KB |
実行使用メモリ | 42,584 KB |
最終ジャッジ日時 | 2025-10-05 16:33:27 |
合計ジャッジ時間 | 12,330 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用 // 警告の抑制 #define _CRT_SECURE_NO_WARNINGS // ライブラリの読み込み #include <bits/stdc++.h> using namespace std; // 型名の短縮 using ll = long long; using ull = unsigned long long; // -2^63 ~ 2^63 = 9e18(int は -2^31 ~ 2^31 = 2e9) using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>; using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>; using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>; using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>; using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>; template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; using Graph = vvi; // 定数の定義 const double PI = acos(-1); int DX[4] = { 1, 0, -1, 0 }; // 4 近傍(下,右,上,左) int DY[4] = { 0, 1, 0, -1 }; int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF; // 入出力高速化 struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp; // 汎用マクロの定義 #define all(a) (a).begin(), (a).end() #define sz(x) ((int)(x).size()) #define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x))) #define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x))) #define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");} #define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順 #define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順 #define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順 #define repe(v, a) for(const auto& v : (a)) // a の全要素(変更不可能) #define repea(v, a) for(auto& v : (a)) // a の全要素(変更可能) #define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索(昇順) #define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素(昇順) #define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て(昇順) #define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去 #define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了 #define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定 // 汎用関数の定義 template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; } template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新(更新されたら true を返す) template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新(更新されたら true を返す) template <class T> inline int getb(T set, int i) { return (set >> i) & T(1); } template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod // 演算子オーバーロード template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; } template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; } template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; } template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; } #endif // 折りたたみ用 #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; #ifdef _MSC_VER #include "localACL.hpp" #endif using mint = modint998244353; //using mint = static_modint<(int)1e9+7>; //using mint = modint; // mint::set_mod(m); using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>; #endif #ifdef _MSC_VER // 手元環境(Visual Studio) #include "local.hpp" #else // 提出用(gcc) int mute_dump = 0; int frac_print = 0; #if __has_include(<atcoder/all>) namespace atcoder { inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; } inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; } } #endif inline int popcount(int n) { return __builtin_popcount(n); } inline int popcount(ll n) { return __builtin_popcountll(n); } inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; } inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; } inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; } inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; } #define dump(...) #define dumpel(v) #define dump_math(v) #define input_from_file(f) #define output_to_file(f) #define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す #endif // 愚直 vm memo((int)1e7 + 1, -1); mint naive1(const string& s) { // Z < n int n = stoi("0" + s); n--; if (n < 0) return 0; mint res = 0; repir(Z, n, 0) { //if (memo[Z] != -1) { // res += memo[Z]; // break; //} repir(Y, Z - 1, 1) { int X = Y - (Z - Y); if (X < 0) break; res++; } } return memo[n] = res; } mint naive2(const string& s) { // X <= n if (s == "") return 0; int n = stoi(s); int ub = powi(10, sz(s)); mint res = 0; repir(X, n, 0) { //if (memo[X] != -1) { // res += memo[X]; // break; //} repi(Y, X + 1, ub - 1) { int Z = Y + (Y - X); if (Z >= ub) break; res++; } } return res; } mint naive3(const string& s) { // Z = n int n = stoi("0" + s); mint res = 0; repir(Z, n, n) { repir(Y, Z - 1, 1) { int X = Y - (Z - Y); if (X < 0) break; res++; } } return res; } mint naive(const string& s) { return naive2(s); } //【行列】 /* * Matrix<T>(int n, int m) : O(n m) * n×m 零行列で初期化する. * * Matrix<T>(int n) : O(n^2) * n×n 単位行列で初期化する. * * Matrix<T>(vvT a) : O(n m) * 二次元配列 a[0..n)[0..m) の要素で初期化する. * * bool empty() : O(1) * 行列が空かを返す. * * A + B : O(n m) * n×m 行列 A, B の和を返す.+= も使用可. * * A - B : O(n m) * n×m 行列 A, B の差を返す.-= も使用可. * * c * A / A * c : O(n m) * n×m 行列 A とスカラー c のスカラー積を返す.*= も使用可. * * A * x : O(n m) * n×m 行列 A と n 次元列ベクトル x の積を返す. * * x * A : O(n m)(やや遅い) * m 次元行ベクトル x と n×m 行列 A の積を返す. * * A * B : O(n m l) * n×m 行列 A と m×l 行列 B の積を返す. * * Mat pow(ll d) : O(n^3 log d) * 自身を d 乗した行列を返す. */ template <class T> struct Matrix { int n, m; // 行列のサイズ(n 行 m 列) vector<vector<T>> v; // 行列の成分 // n×m 零行列で初期化する. Matrix(int n, int m) : n(n), m(m), v(n, vector<T>(m)) {} // n×n 単位行列で初期化する. Matrix(int n) : n(n), m(n), v(n, vector<T>(n)) { rep(i, n) v[i][i] = T(1); } // 二次元配列 a[0..n)[0..m) の要素で初期化する. Matrix(const vector<vector<T>>& a) : n(sz(a)), m(sz(a[0])), v(a) {} Matrix() : n(0), m(0) {} // 代入 Matrix(const Matrix&) = default; Matrix& operator=(const Matrix&) = default; // アクセス inline vector<T> const& operator[](int i) const { return v[i]; } inline vector<T>& operator[](int i) { // verify : https://judge.yosupo.jp/problem/matrix_product // inline を付けて [] でアクセスするとなぜか v[] への直接アクセスより速くなった. return v[i]; } // 入力 friend istream& operator>>(istream& is, Matrix& a) { rep(i, a.n) rep(j, a.m) is >> a.v[i][j]; return is; } // 行の追加 void push_back(const vector<T>& a) { Assert(sz(a) == m); v.push_back(a); n++; } // 行の削除 void pop_back() { Assert(n > 0); v.pop_back(); n--; } // サイズ変更 void resize(int n_) { v.resize(n_); n = n_; } void resize(int n_, int m_) { n = n_; m = m_; v.resize(n); rep(i, n) v[i].resize(m); } // 空か bool empty() const { return min(n, m) == 0; } // 比較 bool operator==(const Matrix& b) const { return n == b.n && m == b.m && v == b.v; } bool operator!=(const Matrix& b) const { return !(*this == b); } // 加算,減算,スカラー倍 Matrix& operator+=(const Matrix& b) { rep(i, n) rep(j, m) v[i][j] += b[i][j]; return *this; } Matrix& operator-=(const Matrix& b) { rep(i, n) rep(j, m) v[i][j] -= b[i][j]; return *this; } Matrix& operator*=(const T& c) { rep(i, n) rep(j, m) v[i][j] *= c; return *this; } Matrix operator+(const Matrix& b) const { return Matrix(*this) += b; } Matrix operator-(const Matrix& b) const { return Matrix(*this) -= b; } Matrix operator*(const T& c) const { return Matrix(*this) *= c; } friend Matrix operator*(const T& c, const Matrix<T>& a) { return a * c; } Matrix operator-() const { return Matrix(*this) *= T(-1); } // 行列ベクトル積 : O(m n) vector<T> operator*(const vector<T>& x) const { vector<T> y(n); rep(i, n) rep(j, m) y[i] += v[i][j] * x[j]; return y; } // ベクトル行列積 : O(m n) friend vector<T> operator*(const vector<T>& x, const Matrix& a) { vector<T> y(a.m); rep(i, a.n) rep(j, a.m) y[j] += x[i] * a[i][j]; return y; } // 積:O(n^3) Matrix operator*(const Matrix& b) const { // verify : https://judge.yosupo.jp/problem/matrix_product Matrix res(n, b.m); rep(i, res.n) rep(k, m) rep(j, res.m) res[i][j] += v[i][k] * b[k][j]; return res; } Matrix& operator*=(const Matrix& b) { *this = *this * b; return *this; } // 累乗:O(n^3 log d) Matrix pow(ll d) const { // verify : https://judge.yosupo.jp/problem/pow_of_matrix Matrix res(n), pow2 = *this; while (d > 0) { if (d & 1) res *= pow2; pow2 *= pow2; d >>= 1; } return res; } #ifdef _MSC_VER friend ostream& operator<<(ostream& os, const Matrix& a) { rep(i, a.n) { os << "["; rep(j, a.m) os << a[i][j] << " ]"[j == a.m - 1]; if (i < a.n - 1) os << "\n"; } return os; } #endif }; //【行簡約形(行交換なし)】O(n m min(n, m)) /* * 行基本変形(行交換なし)で n×m 行列 A を行簡約形に変形し,ピボット位置のリストを返す. */ template <class T> vector<pii> row_reduced_form(Matrix<T>& A) { int n = A.n, m = A.m; vector<pii> piv; piv.reserve(min(n, m)); // 未確定の列を記録しておくリスト list<int> rjs; rep(j, m) rjs.push_back(j); rep(i, n) { // 第 i 行の係数を左から走査し非 0 を見つける. auto it = rjs.begin(); for (; it != rjs.end(); it++) if (A[i][*it] != 0) break; // 第 i 行の全てが 0 なら無視する. if (it == rjs.end()) continue; // A[i][j] をピボットに選択する. int j = *it; rjs.erase(it); piv.emplace_back(i, j); // A[i][j] が 1 になるよう行全体を A[i][j] で割る. T Aij_inv = T(1) / A[i][j]; repi(j2, j, m - 1) A[i][j2] *= Aij_inv; // 第 i 行以外の第 j 列の成分が全て 0 になるよう第 i 行を定数倍して減じる. rep(i2, n) if (A[i2][j] != 0 && i2 != i) { T mul = A[i2][j]; repi(j2, j, m - 1) A[i2][j2] -= A[i][j2] * mul; } } return piv; } //【逆行列】O(n^3) /* * n 次正方行列 mat の逆行列を返す(存在しなければ空) */ template <class T> Matrix<T> inverse_matrix(const Matrix<T>& mat) { // verify : https://judge.yosupo.jp/problem/inverse_matrix int n = mat.n; // 元の行列 mat と単位行列を繋げた拡大行列 v を作る. vector<vector<T>> v(n, vector<T>(2 * n)); rep(i, n) rep(j, n) { v[i][j] = mat[i][j]; if (i == j) v[i][n + j] = 1; } int m = 2 * n; // 注目位置を (i, j)(i 行目かつ j 列目)とする. int i = 0, j = 0; // 拡大行列に対して行基本変形を行い,左側を単位行列にすることを目指す. while (i < n && j < m) { // 同じ列の下方の行から非 0 成分を見つける. int i2 = i; while (i2 < n && v[i2][j] == T(0)) i2++; // 見つからなかったら全て 0 の列があったので mat は非正則 if (i2 == n) return Matrix<T>(); // 見つかったら i 行目とその行を入れ替える. if (i != i2) swap(v[i], v[i2]); // v[i][j] が 1 になるよう行全体を v[i][j] で割る. T vij_inv = T(1) / v[i][j]; repi(j2, j, m - 1) v[i][j2] *= vij_inv; // v[i][j] と同じ列の成分が全て 0 になるよう i 行目を定数倍して減じる. rep(i2, n) { // i 行目だけは引かない. if (i2 == i) continue; T mul = v[i2][j]; repi(j2, j, m - 1) v[i2][j2] -= v[i][j2] * mul; } // 注目位置を右下に移す. i++; j++; } // 拡大行列の右半分が mat の逆行列なのでコピーする. Matrix<T> mat_inv(n, n); rep(i, n) rep(j, n) mat_inv[i][j] = v[i][n + j]; return mat_inv; } // 遷移行列の係数を計算し,埋め込み用のコードを出力する. pair<vector<Matrix<mint>>, vm> embed_coefs(int COL, int len_max, int L_max, int loop_cnt, const vector<string>& ssT_ini = { "" }, const vector<string>& ssB_ini = { "" }) { mt19937_64 mt((int)time(NULL)); uniform_int_distribution<int> rnd_len(1, len_max); uniform_int_distribution<int> rnd_col(0, COL - 1); uniform_int_distribution<int> rnd(0, INF); vector<string> ssT(ssT_ini), ssB(ssB_ini); rep(loop, loop_cnt) { if (loop % 10 == 1) { dump("loop:", loop, "L:", sz(ssT)); // 途中再開用 sort(all(ssT)); sort(all(ssB)); string eb = "vvi ssT = {"; repe(s, ssT) { eb += "{"; repe(c, s) { eb += to_string((int)(c - '0')); eb += ","; } if (eb.back() == ',') eb.pop_back(); eb += "},"; } if (eb.back() == ',') eb.pop_back(); eb += "};\n"; eb += "vvi ssB = {"; repe(s, ssB) { eb += "{"; repe(c, s) { eb += to_string((int)(c - '0')); eb += ","; } if (eb.back() == ',') eb.pop_back(); eb += "},"; } if (eb.back() == ',') eb.pop_back(); eb += "};\n"; cerr << eb; } // 候補とする文字列をランダムに L_max 個追加する. rep(hoge, L_max) { int len = rnd_len(mt); string s; rep(fuga, len) s += '0' + rnd_col(mt); ssT.push_back(s); } rep(hoge, L_max) { int len = rnd_len(mt); string s; rep(fuga, len) s += '0' + rnd_col(mt); ssB.push_back(s); } uniq(ssT); uniq(ssB); // (i,j) 成分が naive(ss[i] + ss[j]) であるような行列 mat を得る. int LT = sz(ssT), LB = sz(ssB); Matrix<mint> mat(LT, LB); rep(i, LT) rep(j, LB) mat[i][j] = naive(ssT[i] + ssB[j]); // mat に対して行基本変形を行いピボット位置のリスト piv を得る. auto piv = row_reduced_form(mat); // ランク上昇に寄与した文字列だけ残す. vector<string> nssT, nssB; for (auto [i, j] : piv) { nssT.push_back(ssT[i]); nssB.push_back(ssB[j]); } ssT = move(nssT); ssB = move(nssB); } // (i,j) 成分が naive(ss[i] + ss[j]) であるような行列 mat を得る. int LT = sz(ssT), LB = sz(ssB); Matrix<mint> mat(LT, LB); rep(i, LT) rep(j, LB) mat[i][j] = naive(ssT[i] + ssB[j]); // mat に対して行基本変形を行いピボット位置のリスト piv を得る. auto piv = row_reduced_form(mat); int DIM = sz(piv); // 選択した行 is と列 js を並べ直して "" 始まりにする. vi is(DIM), js(DIM); rep(r, DIM) tie(is[r], js[r]) = piv[r]; repi(i, 1, DIM - 1) if (ssT[is[i]] == "") swap(is[i], is[0]); repi(j, 1, DIM - 1) if (ssB[js[j]] == "") swap(js[j], js[0]); if (ssT[is[0]] != "" || ssB[js[0]] != "") { dump("ERROR! ssT[is[0]]:", ssT[is[0]], "ssB[js[0]]:", ssB[js[0]]); exit(-1); } // 基底の変換行列 P を得る. Matrix<mint> matP(DIM, DIM); rep(i, DIM) rep(j, DIM) matP[i][j] = naive(ssT[is[i]] + ssB[js[j]]); // P の逆行列 P_inv を得る. auto matP_inv = inverse_matrix(matP); // 各文字に対応する表現行列を得る. vector<Matrix<mint>> matAs(COL, Matrix<mint>(DIM, DIM)); rep(k, COL) { char c = '0' + k; rep(i, DIM) rep(j, DIM) matAs[k][i][j] = naive(ssT[is[i]] + c + ssB[js[j]]); matAs[k] = matAs[k] * matP_inv; } // 右端を閉じるためのベクトルを得る. vm vecP(DIM); rep(i, DIM) vecP[i] = matP[i][0]; // 埋め込み用の文字列を出力する. auto to_signed_string = [](mint x) { int v = x.val(); int mod = mint::mod(); if (2 * v > mod) v -= mod; return to_string(v); }; string eb = "constexpr int DIM = "; eb += to_string(DIM); eb += ";\n"; eb += "constexpr int COL = "; eb += to_string(COL); eb += ";\n"; eb += "VTYPE matAs[COL][DIM][DIM] = {\n"; rep(c, COL) { eb += "{"; rep(i, DIM) { eb += "{"; rep(j, DIM) eb += to_signed_string(matAs[c][i][j]) + ","; eb.pop_back(); eb += "},"; } eb.pop_back(); eb += "},\n"; } eb.pop_back(); eb.pop_back(); eb += "};\n"; eb += "VTYPE vecP[DIM] = {"; rep(i, DIM) eb += to_signed_string(vecP[i]) + ","; eb.pop_back(); eb += "};\n"; cout << eb; dump("sz(eb):", sz(eb)); exit(0); return { matAs, vecP }; } template <class VTYPE> VTYPE solve(const string& s) { // --------------- embed_coefs() からの出力を貼る ---------------- constexpr int DIM = 4; constexpr int COL = 10; VTYPE matAs[COL][DIM][DIM] = { {{1,0,0,0},{21,-20,-30,30},{56,-55,-70,70},{176,-175,-200,200}}, {{-332748117,332748117,332748119,-332748118},{24,-24,-32,33},{-332748057,332748057,332748044,-332748043},{184,-184,-207,208}}, {{0,1,0,0},{-332748091,332748092,332748081,-332748081},{65,-64,-80,80},{-332747926,332747927,332747901,-332747901}}, {{0,0,1,0},{30,-30,-39,40},{70,-70,-84,85},{200,-200,-224,225}}, {{-332748118,332748119,332748117,-332748117},{33,-32,-44,44},{-332748043,332748044,332748027,-332748027},{208,-207,-234,234}}, {{0,0,0,1},{-332748081,332748081,332748071,-332748070},{80,-80,-95,96},{-332747901,332747901,332747876,-332747875}}, {{0,1,-2,2},{40,-39,-52,52},{85,-84,-102,102},{225,-224,-252,252}}, {{-332748117,332748117,332748116,-332748115},{44,-44,-55,56},{-332748027,332748027,332748011,-332748010},{234,-234,-260,261}}, {{1,0,-4,4},{-332748070,332748071,332748057,-332748057},{96,-95,-114,114},{-332747875,332747876,332747847,-332747847}}, {{2,-2,-4,5},{52,-52,-64,65},{102,-102,-119,120},{252,-252,-279,280}} }; VTYPE vecP[DIM] = { 0,0,1,4 }; // -------------------------------------------------------------- // ここ以降は書き換えなくて良い. array<VTYPE, DIM> dp; dp[0] = 1; repi(i, 1, DIM - 1) dp[i] = 0; auto apply = [&](const array<VTYPE, DIM>& x, int col) { array<VTYPE, DIM> z; rep(j, DIM) { z[j] = 0; rep(i, DIM) z[j] += x[i] * matAs[col][i][j]; } return z; }; repe(c, s) { dp = apply(dp, c - '0'); } VTYPE res = 0; rep(i, DIM) res += dp[i] * vecP[i]; return res; } template <class VTYPE> VTYPE solve2(const string& s) { // --------------- embed_coefs() からの出力を貼る ---------------- constexpr int DIM = 5; constexpr int COL = 10; VTYPE matAs[COL][DIM][DIM] = { {{0,1,0,0,0},{0,0,1,0,0},{0,-10,11,0,0},{-8960,9846,-9850,17920,-8955},{-17820,19592,-19601,35640,-17810}}, {{90,-98,98,-179,90},{0,0,0,1,0},{-900,980,-980,1801,-900},{-9850,10825,-10830,19701,-9845},{-18700,20560,-20570,37401,-18690}}, {{180,-197,197,-360,181},{0,0,0,0,1},{-1800,1970,-1970,3600,-1799},{-10740,11804,-11809,21480,-10734},{-19580,21528,-21538,39160,-19569}}, {{272,399297443,-399297444,-543,273},{2,399297739,-399297740,-3,3},{-2698,399300699,-399300700,5397,-2697},{-11628,399310522,-399310528,23257,-11622},{-20458,399320235,-399320246,40917,-20447}}, {{364,-199649270,199649269,-728,366},{4,-199648875,199648874,-8,6},{-3596,-199644925,199644924,7192,-3594},{-12516,-199635113,199635107,25032,-12509},{-21336,-199625411,199625400,42672,-21324}}, {{458,-399298244,399298242,-915,460},{8,-399297750,399297748,-15,10},{-4492,-399292810,399292808,8985,-4490},{-13402,-399283009,399283002,26805,-13395},{-22212,-399273318,399273306,44425,-22200}}, {{552,399297135,-399297137,-1104,555},{12,399297728,-399297730,-24,15},{-5388,399303658,-399303660,10776,-5385},{-14288,399313448,-399313455,28576,-14280},{-23088,399323128,-399323140,46176,-23075}}, {{648,-399298453,399298450,-1295,651},{18,-399297761,399297758,-35,21},{-6282,-399290841,399290838,12565,-6279},{-15172,-399281062,399281054,30345,-15164},{-23962,-399271393,399271380,47925,-23949}}, {{744,-199649688,199649685,-1488,748},{24,-199648897,199648894,-48,28},{-7176,-199640987,199640984,14352,-7172},{-16056,-199631219,199631211,32112,-16047},{-24836,-199621561,199621548,49672,-24822}}, {{842,399296816,-399296820,-1683,846},{32,399297706,-399297710,-63,36},{-8068,399306606,-399306610,16137,-8064},{-16938,399316363,-399316372,33877,-16929},{-25708,399326010,-399326024,51417,-25694}} }; VTYPE vecP[DIM] = { 0,4,49,98,146 }; // -------------------------------------------------------------- // ここ以降は書き換えなくて良い. array<VTYPE, DIM> dp; dp[0] = 1; repi(i, 1, DIM - 1) dp[i] = 0; auto apply = [&](const array<VTYPE, DIM>& x, int col) { array<VTYPE, DIM> z; rep(j, DIM) { z[j] = 0; rep(i, DIM) z[j] += x[i] * matAs[col][i][j]; } return z; }; repe(c, s) { dp = apply(dp, c - '0'); } VTYPE res = 0; rep(i, DIM) res += dp[i] * vecP[i]; return res; } template <class VTYPE> VTYPE solve3(const string& s) { // --------------- embed_coefs() からの出力を貼る ---------------- constexpr int DIM = 3; constexpr int COL = 10; VTYPE matAs[COL][DIM][DIM] = { {{1,0,0},{-4,0,5},{-9,0,10}}, {{0,1,0},{-5,1,5},{-10,1,10}}, {{0,0,1},{-5,0,6},{-10,0,11}}, {{-1,1,1},{-6,1,6},{-11,1,11}}, {{-1,0,2},{-6,0,7},{-11,0,12}}, {{-2,1,2},{-7,1,7},{-12,1,12}}, {{-2,0,3},{-7,0,8},{-12,0,13}}, {{-3,1,3},{-8,1,8},{-13,1,13}}, {{-3,0,4},{-8,0,9},{-13,0,14}}, {{-4,1,4},{-9,1,9},{-14,1,14}} }; VTYPE vecP[DIM] = { 0,0,1 }; // -------------------------------------------------------------- // ここ以降は書き換えなくて良い. array<VTYPE, DIM> dp; dp[0] = 1; repi(i, 1, DIM - 1) dp[i] = 0; auto apply = [&](const array<VTYPE, DIM>& x, int col) { array<VTYPE, DIM> z; rep(j, DIM) { z[j] = 0; rep(i, DIM) z[j] += x[i] * matAs[col][i][j]; } return z; }; repe(c, s) { dp = apply(dp, c - '0'); } VTYPE res = 0; rep(i, DIM) res += dp[i] * vecP[i]; return res; } int main() { input_from_file("input.txt"); // output_to_file("output.txt"); //【方法】 // 愚直を書いて集めたデータをもとに遷移行列を復元する. //【使い方】 // 1. mint naive(文字列) を実装する. // 2. embed_coefs(文字の種類数); を実行する. // 3. 出力を solve() 内に貼る. // 4. auto dp = solve<答えの型>(文字列) で勝手に DP してくれる. dump("naive:", naive("3")); dump("====="); dump("naive:", naive("10")); dump("====="); dump("naive:", naive("0")); dump("====="); vector<string> ssT_ini{ "" }, ssB_ini{ "" }; // embed_coefs(10, 2, 10, 22, ssT_ini, ssB_ini); // n=30 // 012 / 210,321,432,543,654,765,876,978,420,531,642,753,846,957,630,741,852,963,840,951 int T; cin >> T; rep(hoge, T) { ll n; int K; cin >> n >> K; n--; string s = to_string(n); while (sz(s) < 18) s = "0" + s; string sh = s.substr(0, 18 - K); string sl = s.substr(18 - K); string pow10 = "1"; rep(hoge, K) pow10 += '0'; auto c1 = solve<mint>(sh); auto c2 = solve<mint>(pow10); auto c3 = solve3<mint>(sh); auto c4 = solve2<mint>(sl); dump(c1, c2, c3, c4); mint res = c1 * c2 + c3 * c4; cout << res << "\n"; } }