結果
問題 |
No.3242 Count 8 Included Numbers (Hard)
|
ユーザー |
![]() |
提出日時 | 2025-08-22 23:23:10 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,103 bytes |
コンパイル時間 | 423 ms |
コンパイル使用メモリ | 12,288 KB |
実行使用メモリ | 44,696 KB |
最終ジャッジ日時 | 2025-08-22 23:23:32 |
合計ジャッジ時間 | 4,415 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 1 TLE * 1 -- * 18 |
ソースコード
mod = 998244353 N = input() n = len(N) summ = 0 for i in range(n-1,-1,-1): digit = n-(i+1) summ += int(N[i])*pow(10,digit,mod) summ %= mod #print(summ) dp = [[[0,0] for _ in range(10)] for _ in range(n)] for i in range(1,int(N[0])): if i!=8: dp[0][i][0] = 1 if int(N[0])!=8: dp[0][int(N[0])][1] = 1 for d in range(1,n): for i in range(1,10): if i!=8: dp[d][i][0] += 1 for i in range(10): if i==8: continue for j in range(10): if j==8: continue dp[d][j][0] += dp[d-1][i][0] dp[d][j][0] %= mod if int(N[d-1])==8: continue for j in range(int(N[d])): if j==8: continue dp[d][j][0] += dp[d-1][int(N[d-1])][1] dp[d][j][0] %= mod if int(N[d])==8: continue dp[d][int(N[d])][1] += dp[d-1][int(N[d-1])][1] dp[d][int(N[d])][1] %= mod cnt = 0 #for i in range(2): # print(dp[i]) for i in range(10): if i==8: continue cnt += dp[-1][i][0]+dp[-1][i][1] cnt %= mod print((summ-cnt)%mod)