結果
| 問題 |
No.3242 Count 8 Included Numbers (Hard)
|
| ユーザー |
 矢澤式WINTER
|
| 提出日時 | 2025-08-22 22:23:42 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 124 ms / 2,000 ms |
| コード長 | 9,414 bytes |
| コンパイル時間 | 6,057 ms |
| コンパイル使用メモリ | 339,204 KB |
| 実行使用メモリ | 20,092 KB |
| 最終ジャッジ日時 | 2025-08-22 22:24:21 |
| 合計ジャッジ時間 | 7,964 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 20 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
/*
winter's kyopro template
*/
//*/
#include <atcoder/all>
using namespace atcoder;
//*/
// ......Jgg+.
// ..jQHHMHHHHMMHHMNHHmaJ+&&ga&&J-.... ..(-.
// .JdMHMM@@@@@MMHyyyWHHWMHHMMM@MMMHHHMMMNmmm&-..&HMMMMMm.
// .(WHM@@@@@@@@MMWyyWWWH@@@@@g@@@@@MH@@@@@@@@MMHMMMHVyyVHMNHHHm.
// .dMM@@@@@@@@@MHVWWWMMM@@@@@@@@@@@@@@@@@@@@@@@@@@@MkWWWHHHWyyHMn.
// .dH@@@@MMMMHHHWWHWH@@@@@@@@@@@g@@@@g@@@@@@@@@@@@@@@MMHyyyyyyyWHMNma..
// (WH@@@@NWyyyWWHUuuuXWH@@@@@@@@@@@g@@@@@@M@@@@@@g@@@@@HHkyyyyyVH@@@MMHNm,
// (WH@@@@@@HyyWHUuuuuuuuuXWHHHH@@@@@@@g@@@@@MM@@@@@@@@@@HUWkyyyyWM@@@@@@MMNm-
// .dH@@@@@@@MkWHkkkkkkXuuuuuuuuXWUWHHHHHHHg@@g@MHHg@@HHHUuuuWkyyyyWM@@@@@@@MMH+
// .dMM@@@g@@MHHM@@@@@@@HHkkkXuuuWSuuuuuuuuuuuuXXXUHkXuuuuuuuuXHkyyyyWHM@@@@@@MHNe.
// (MM@@@@@@@NW@@@@@@MM@@@@@@@HHWHkkXuuuuuuuuuuuuuuuUHkuuuuuuuuXHWyyyyyVHM@@@g@@MNl
// .WH@@@@@@@@@M@@@@@MM@@@@@@@M9=d@@@@gHHHHkkkkkkQQQQQkHkQkkHHHkkWkyyyyyyyWH@@@@@MHH-
// .dH@@@@@g@@@H@@@@@MM@@@@@@H9! (W@@@@@@@@MM@@@@@@@@@@@@MM@@@@@@@@HVyyyyyWWW@@@@@@MNr
// (HM@@@@@@@@MM@@@@@M@g@@@@B:``.(@@@@@@@@@MH@@@@@@@@@@@@@MM@@@@@@@MHWWkWqH@@@@@@@@MHH_
// .dHM@@@@g@@@H@@@@@H@@@@@M3_`.` J@@@@@@@@@H?H@@@@@@@@@@@@@HM@@@g@@@@HHWyyVH@@@@@@@@HH~
// dMM@@@@@@@@HM@@@@@H@@g@#>..... dM@@@g@@@@D.?H@@@@@g@@g@@@@M@@@@@@@@HVWWWH@@@@@g@@@HN-
// .dMM@@@@g@@gMH@@@@@M@@@@#><?zw&. j@@@@@@g@M>` ?M@@@@@@@@@@@@H@@@@@@@@MH@M@@@@@@@@@@@HM{
// .dMM@@@@@@@@@M@@@@g@H@@@#!```` _?IjH@@@@@@M$_``.?H@@@@@@g@@@@M@@@g@@@@M@@@@@@@@@@@@@@HM>
// ..jHH@@@@@g@@g@MM@@@@@@HM@MC......`.`_W@@@@@@D_..-J+dMMM@MM@@@g@H@@@@@@@MH@@@@@@@@@g@@@MHD`
// .gHHQHMMM@@@@@@@@@@MHM@@@@g@@HM@D~.(ggNQma,.jH@MM@#~.-~~_.. ?WMMHM@@@@H@@@@g@@HHM@@@@@g@@@g@@MMD
// ZMHM@@@@@@@@@@@@@MHM@@@@@@@MHMMI+MB=?HNHHMn-U@MMM{.````.``.. ?TMMM@@@M@g@@@@@H@H@@@g@@@@@@@@HM$
// ?WMHMHM@@@@@@g@MM@@@Nc?H@MHMMNd#:+-.dMMNZ>.(WN?U:`.`.``.```.`._!_TMM@@@@g@@MM@MM@@@@@g@@@@@H#:
// .+MHM@@@@@@@@@MM@@@@@No(HHHVUWN{(MMMMMMMb_`.-?!`.`...-((-..`.`.`. (M@@@@@@@H@@M#M@@@@@g@@@MHR
// (dMM@@@@@@@@@MHMHWHM@@M81zHD_dMN<(MMMMMMMD_``.``.`. (JgggJ.<!.``. (H@@@g@@@M@@@MMH@@g@@@@@@MHR
// +MM@@@@@@@@MMHHM@Nm._79!<-(>`(wI?3-?MHWWM@!.`.`.`.`.(TYYYHMMNe..`.(H@@@@@@MHM@@MM@@@@@@@@g@@MHR
// jMHMMM@@@@MMM@@HM@@@@H+ <i(w> jK>:~~__<?7!_``.`.`.`.``.``.` _7MMs(d@@@@@@@MWM@@MHM@@@@@@@g@@@MHD
// dHH#M@@@MMM9>?WH@@@MM@N;. ~!.jMH<:::::_`.``.`..`.``.`.`.`... .(WHMM@@@@HY! dHHHHM@@@@@g@@@@@MMr
// dHHM@@@MM9! dHM@MHM@#Nx `` ?MN<_____.`.`......`.``.`.`._~:::((ud@@HH9=``` jH@HH@@@@@@@@@@@@MMR.
// vMHM@MH#> dMM@HHHMMHM2 `.`?MN, ````.`..jUwz?>++. ``.`_~~:?TY9Y=<~_``...dM9TMH@@M@@@@g@@g@@HH_
// OMM@H#: .WMHHH@@MMHN;.`.`_TMm. `.```.jZ=====zw:.``.`..`````..-JJJggHHY! .HH@MHM@@@@@@@@@HN{
// .dHMHR _WMHHMC!?TMN+.`.`._vHW&...``.?====zz>_`.`.``````..JdMBYTY^` .WH@HHMM@@@g@MM@MMR.
// (MMHR_ _7T=` (MN+``.` (wXWUUO+-.. _~<<`.`.`..` .-JgHMHHH, dMM@HHHM@@@@@MHMHNe.
// (TH9! (HNx..`.wdyykX<(HWH4Z1++(((JJ&zwXWWWHHWWXMNo TMH@MHH@@@@@HHHH#MH+
// (WMm&(wwXyyyXXdkW0`.`.`. dWyR+uwyyyyyyyWwHN{ ?THMMH@@@@@HMY7TMHC
// jMSXSwyyyyyyWXUWH......(dHWUXXyyyyyyyyykXMHe. dMM@@@MH#~
// dMHXXyyyyyyyWWyXkwXZuuuwXwuUyyyyyyyyyyykwvdMm. J@M@@@MMD`
// (TMM@HHQQkkkWHyyyyyyyyyy0<:;zyyyyyyyyyXXf~_WN- .dH@@@HM@!
// `??TYYYWHMMWyyyyyyyyyWA&uwyyWHkyyyUwVC((dMMMH_ .HH@@MM8!
// vMNWyyyyyyyyyyyyyyyyyWHkQHmdWWyyWHMD` .dMMMM#=`
// 7MMkyyyyyyyyyyyyyyyyyWWHMMkWWWWMMHH+ JMMM9=`
// (TMMHkWyyyyyyyyyyyyyWHWkWH9Y<zUV<WN; ?!`
// .(d@HMHWkkWyyyyyyyVWHHM8w+ ` _.(HNo.
// .(gkHHMMMMNWyyWWWWVyyypHpW0z;<zO++zV9?WN;
// (WMM9UOOTUv?WWkWVVVWWWWU0CzXz;;;;;;+Z:-dM{
// (MR~1+-<.(w++<?TH9TC1<;;;;;?1;;>;;+v:(dMD`
// ?MH+?1-.._<zz;vC;;;;>++;;>;>;;;;+wC<&dN:
// `(M#!_?u-..(z&++>;;<jV<;>;;;>>>+jZ~(dM=
// .TMm+JZ1--_._~?zz&u9Twzz&&zZ77<!(WMB^
// (WHB1-_(z_..(-____..~_~~_.._-JW#>
// .gHMB! <<.(1(JXQe+((+<<<1+(+1WMMY`
// .dM9!_~```-?1-.(dMD<<<<<(-....dMC
// (W#! ````````` (dH@~````` _?<.dM=
// (H8````````` .(HHM}` `````` (WB!
// .d#:`` ```` .JHMHM#~``` `` .(M9!
// `(MD ` ````.JkM9=`(H$`````` jM$
// (@{``` ` (HB>` (@l ` `` `.WK~
// .dMx ``.jM3` JM{``` ```.MK`
// .WHHA<+(dMC dM>````` `(M$
// dHH$_(WM3 dN: ``` ` dN{
// ?MHmJdH#! .d#~` ````-WD`
// ?TTB9! (Mb- ` ` .dM>
// .dH9!(A-. .dM%
// (MNI-.dWyVQd#>
// .TMm+?UVWWM#>
// ?WMHmdMM9!
// _?7T=!
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define ALL(x) (x).begin(),(x).end()
#define dbgv(x); for(auto now : x) cout << now << " "; cout << endl;
//using P = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
//*/
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vint;
random_device rnd;
mt19937 rng(rnd());
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int dx2[8] = {1,1,1,0,-1,-1,-1,0};
const int dy2[8] = {0,1,-1,1,0,1,-1,-1};
using mint = modint998244353;
struct UnionFind {
vector<int> par;
UnionFind(int n=0): par(n,-1) {}
int find(int x) {
if(par[x] < 0) return x;
return par[x] = find(par[x]);
}
bool unite(int x, int y){
x = find(x); y = find(y);
if(x==y) return false;
if(par[x] > par[y]) swap(x,y);
par[x] += par[y];
par[y] = x;
return true;
}
bool same(int x, int y) {return find(x) == find(y);}
int size(int x) {return -par[find(x)];}
};
struct modinv {
int n; vector<mint> d;
modinv(): n(2), d({0,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(-d[mint::mod()%n]*(mint::mod()/n)), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} invs;
struct modfact {
int n; vector<mint> d;
modfact(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*n), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} facts;
struct modfactinv {
int n; vector<mint> d;
modfactinv(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*invs(n)), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} ifacts;
mint comb(int n, int k) {
if (n < k || k < 0) return 0;
return facts(n)*ifacts(k)*ifacts(n-k);
}
using mint = modint998244353;
mint dp[1000000][2][2];
void solve(){
string n; cin >> n;
mint ans = 0;
// mint coef = (n.size() > 1),al = (n.size() > 1);
// rep(i,n.size()-1){
// al = al*10;
// coef *= 9;
// }
// mint var = al-coef;
// ans += var;
// if((int)(n[0]-'0') == 8){
// dp[0][0][1] = 1;
// dp[0][1][0] = 7;
// }else if((int)(n[0]-'0') == 9){
// dp[0][1][1] = 1;
// dp[0][0][0] = 1;
// dp[0][1][0] = 7;
// }else{
// dp[0][0][0] = 1;
// dp[0][1][0] = ((int)(n[0]-'0')-1);
// }
dp[0][0][0] = 1;
rep(i,n.size()){
rep(j,2){
rep(k,2){
if(dp[i][j][k].val() == 0) continue;
int mx = n[i]-'0';
if(j) mx = 9;
rep(now,mx+1){
dp[i+1][j||(now<mx)][k||(now==8)] += dp[i][j][k];
}
}
}
//cerr << dp[i][0][0].val() << " " << dp[i][0][1].val() << " " << dp[i][1][0].val() << " " << dp[i][1][1].val() << endl;
}
//cout << ans.val() << endl;
ans += dp[n.size()][0][1] + dp[n.size()][1][1];
cout << ans.val() << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(25);
int t = 1; //cin >> t;
rep(testcase,t) solve();
}