結果
問題 |
No.3242 Count 8 Included Numbers (Hard)
|
ユーザー |
![]() |
提出日時 | 2025-08-22 23:41:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,700 bytes |
コンパイル時間 | 3,088 ms |
コンパイル使用メモリ | 281,852 KB |
実行使用メモリ | 177,772 KB |
最終ジャッジ日時 | 2025-08-22 23:41:59 |
合計ジャッジ時間 | 10,593 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 13 WA * 7 |
ソースコード
#include<iostream> #include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ string N; ll n, summ, digit, pow; ll mod = 998244353; cin >> N; n = N.size(); summ = 0; pow = 1; for (int i = n-1; i>-1; i--){ digit = n-(i+1); summ += ((N[i]-'0')*pow)%mod; summ %= mod; pow = (pow*10)%mod; } vector<vector<array<ll,2>>> dp(n, vector<array<ll,2>>(10,{0,0})); for (int i=1; i<(N[0]-'0'); i++){ if (i!=8){ dp[0][i][0] = 1; } } if ((N[0]-'0')!=8){ dp[0][(N[0]-'0')][1] = 1; } for (int d=1; d<n; d++){ for (int i=1; i<10; i++){ if (i!=8){ dp[d][i][0] += 1; } } for (int i=0; i<10; i++){ if (i==8){ continue; } for (int j=0; j<10; j++){ if (j==8){ continue; } dp[d][j][0] += dp[d-1][i][0]; dp[d][j][0] %= mod; } } if ((N[d-1]-'0')==8){ continue; } for (int j=0; j<(N[d]-'0'); j++){ if (j==8){ continue; } dp[d][j][0] += dp[d-1][(N[d-1]-'0')][1]; dp[d][j][0] %= mod; } if ((N[d]-'0')==8){ continue; } dp[d][(N[d]-'0')][1] += dp[d-1][N[d-1]-'0'][1]; dp[d][(N[d]-'0')][1] %= mod; } ll cnt = 0; for (int i=0; i<10; i++){ if (i==8){ continue; } cnt += dp[n-1][i][0]+dp[n-1][i][1]; cnt %= mod; } cout << (summ-cnt)%mod << endl; }