結果
問題 | No.528 10^9と10^9+7と回文 |
ユーザー | takeya_okino |
提出日時 | 2019-06-28 19:37:09 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,910 bytes |
コンパイル時間 | 2,143 ms |
コンパイル使用メモリ | 75,004 KB |
実行使用メモリ | 65,096 KB |
最終ジャッジ日時 | 2023-09-14 21:29:13 |
合計ジャッジ時間 | 8,683 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 137 ms
60,700 KB |
testcase_01 | AC | 133 ms
58,840 KB |
testcase_02 | AC | 133 ms
58,800 KB |
testcase_03 | AC | 133 ms
58,488 KB |
testcase_04 | AC | 132 ms
58,640 KB |
testcase_05 | AC | 131 ms
58,836 KB |
testcase_06 | AC | 132 ms
58,880 KB |
testcase_07 | AC | 132 ms
58,492 KB |
testcase_08 | AC | 133 ms
58,832 KB |
testcase_09 | AC | 133 ms
58,548 KB |
testcase_10 | AC | 251 ms
64,996 KB |
testcase_11 | AC | 249 ms
62,936 KB |
testcase_12 | AC | 253 ms
62,808 KB |
testcase_13 | AC | 240 ms
60,932 KB |
testcase_14 | AC | 215 ms
60,376 KB |
testcase_15 | AC | 210 ms
63,396 KB |
testcase_16 | AC | 219 ms
60,404 KB |
testcase_17 | AC | 214 ms
59,172 KB |
testcase_18 | AC | 241 ms
63,112 KB |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | AC | 213 ms
58,916 KB |
testcase_22 | AC | 133 ms
58,800 KB |
testcase_23 | AC | 134 ms
56,916 KB |
testcase_24 | AC | 150 ms
59,024 KB |
testcase_25 | AC | 162 ms
58,944 KB |
testcase_26 | AC | 249 ms
63,056 KB |
testcase_27 | AC | 257 ms
65,096 KB |
ソースコード
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String n = sc.next(); int len = n.length(); long ans1 = 0; long ans2 = 0; long M1 = (long)Math.pow(10, 9); long M2 = (long)Math.pow(10, 9) + 7; long[] rui1 = new long[100000]; long[] rui2 = new long[100000]; rui1[0] = 1; rui2[0] = 1; for(int i = 1; i < 100000; i++) { rui1[i] = (rui1[i - 1] * 10) % M1; rui2[i] = (rui2[i - 1] * 10) % M2; } if(len == 1) { int a = Integer.parseInt(n); ans1 = a; ans2 = a; } else { ans1 = 9; ans2 = 9; for(int i = 2; i < len; i++) { int hi = i / 2; if((i % 2) == 0) { ans1 = (ans1 + 9 * rui1[hi - 1]) % M1; ans2 = (ans2 + 9 * rui2[hi - 1]) % M2; } else { ans1 = (ans1 + 9 * rui1[hi]) % M1; ans2 = (ans2 + 9 * rui2[hi]) % M2; } } int p1 = 0; int p2 = 0; int p3 = 0; int hlen = len / 2; long[][] dp1 = new long[hlen][2]; long[][] dp2 = new long[hlen][2]; int first = Integer.parseInt(String.valueOf(n.charAt(0))); dp1[0][0] = 1; dp2[0][0] = 1; dp1[0][1] = first - 1; dp2[0][1] = first - 1; if(len % 2 == 0) { int t = 0; for(int i = 0; i < hlen; i++) { int d1 = Integer.parseInt(String.valueOf(n.charAt(hlen + i))); int d2 = Integer.parseInt(String.valueOf(n.charAt(hlen - i - 1))); if(d1 > d2) { t = 1; p3 = 1; break; } else if(d1 < d2) { t = 1; p1 = 1; break; } } if(t == 0) p2 = 1; for(int i = 1; i < hlen; i++) { int d = Integer.parseInt(String.valueOf(n.charAt(i))); dp1[i][0] = (dp1[i][0] + dp1[i - 1][0]) % M1; dp1[i][1] = (dp1[i][1] + d * dp1[i - 1][0] + 10 * dp1[i - 1][1]) % M1; dp2[i][0] = (dp2[i][0] + dp2[i - 1][0]) % M2; dp2[i][1] = (dp2[i][1] + d * dp2[i - 1][0] + 10 * dp2[i - 1][1]) % M2; } ans1 = (ans1 + dp1[hlen - 1][1]) % M1; ans2 = (ans2 + dp2[hlen - 1][1]) % M2; if((p2 == 1) || (p3 == 1)) { ans1 = (ans1 + dp1[hlen - 1][0]) % M1; ans2 = (ans2 + dp2[hlen - 1][0]) % M2; } } else { int t = 0; for(int i = 1; i <= hlen; i++) { int d1 = Integer.parseInt(String.valueOf(n.charAt(hlen + i))); int d2 = Integer.parseInt(String.valueOf(n.charAt(hlen - i))); if(d1 > d2) { t = 1; p3 = 1; break; } else if(d1 < d2) { t = 1; p1 = 1; break; } } if(t == 0) p2 = 1; for(int i = 1; i < hlen; i++) { int d = Integer.parseInt(String.valueOf(n.charAt(i))); dp1[i][0] = (dp1[i][0] + dp1[i - 1][0]) % M1; dp1[i][1] = (dp1[i][1] + d * dp1[i - 1][0] + 10 * dp1[i - 1][1]) % M1; dp2[i][0] = (dp2[i][0] + dp2[i - 1][0]) % M2; dp2[i][1] = (dp2[i][1] + d * dp2[i - 1][0] + 10 * dp2[i - 1][1]) % M2; } ans1 = (ans1 + dp1[hlen - 1][1] * 10) % M1; ans2 = (ans2 + dp2[hlen - 1][1] * 10) % M2; int d = Integer.parseInt(String.valueOf(n.charAt(hlen))); if(p1 == 1) { ans1 = (ans1 + dp1[hlen - 1][0] * d) % M1; ans2 = (ans2 + dp2[hlen - 1][0] * d) % M2; } if(p2 == 1) { ans1 = (ans1 + dp1[hlen - 1][0] * (d + 1)) % M1; ans2 = (ans2 + dp2[hlen - 1][0] * (d + 1)) % M2; } if(p3 == 1) { ans1 = (ans1 + dp1[hlen - 1][0] * 10) % M1; ans2 = (ans2 + dp2[hlen - 1][0] * 10) % M2; } } } System.out.println(ans1); System.out.println(ans2); } }