結果
問題 |
No.3242 Count 8 Included Numbers (Hard)
|
ユーザー |
![]() |
提出日時 | 2025-08-22 22:23:34 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 391 ms / 2,000 ms |
コード長 | 942 bytes |
コンパイル時間 | 4,339 ms |
コンパイル使用メモリ | 79,740 KB |
実行使用メモリ | 55,104 KB |
最終ジャッジ日時 | 2025-08-22 22:23:58 |
合計ジャッジ時間 | 12,048 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 20 |
ソースコード
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); char[] s = sc.next().toCharArray(); sc.close(); int mod = 998244353; long dp00 = 1; long dp01 = 0; long dp10 = 0; long dp11 = 0; for (int i = 0; i < s.length; i++) { int c = s[i] - '0'; long n00 = 0; long n10 = 0; long n01 = 0; long n11 = 0; if (c < 8) { n00 = dp00; n10 = dp00 * c + dp10 * 9; n01 = dp01; n11 = dp10 + dp01 * c + dp11 * 10; } else { if (c == 8) { n10 = dp00 * c + dp10 * 9; n01 = dp00 + dp01; n11 = dp10 + dp01 * c + dp11 * 10; } else { n00 = dp00; n10 = dp00 * (c - 1) + dp10 * 9; n01 = dp01; n11 = dp00 + dp10 + dp01 * c + dp11 * 10; } } dp00 = n00 % mod; dp10 = n10 % mod; dp01 = n01 % mod; dp11 = n11 % mod; } System.out.println((dp01 + dp11) % mod); } }