結果

問題 No.3242 Count 8 Included Numbers (Hard)
ユーザー Unbakedbread
提出日時 2025-08-24 00:53:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 805 bytes
コンパイル時間 2,636 ms
コンパイル使用メモリ 276,116 KB
実行使用メモリ 18,524 KB
最終ジャッジ日時 2025-08-24 00:53:54
合計ジャッジ時間 4,282 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 998244353;

ll p10[900000], p9[900000];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	p10[0] = 1;
	for(int i = 1; i < 900000; ++i) p10[i] = (p10[i - 1] * 10) % mod;
	p9[0] = 1;
	for(int i = 1; i < 900000; ++i) p9[i] = (p9[i - 1] * 9) % mod;
	
	string N;
	cin >> N;
	int T = N.size();
	
	ll ans = 0;
	bool flag = 0;
	for(int i = 0; i < T; ++i) {
		if(flag) ans = (ans + (N[i] - '0') * p10[T - i - 1] % mod) % mod;
		else {
			for(int j = 0; j < (N[i] - '0'); ++j) {
				if(j == 8) ans = (ans + p10[T - i - 1]) % mod;
				else ans = (ans + p10[T - i - 1] - p9[T - i - 1] + mod) % mod;
			}
		}
		if(N[i] == '8') flag = 1;
	}
	
	if(flag) ans = (ans + 1) % mod;
	
	cout << ans << endl;
	return 0;
}
0