結果
問題 | No.528 10^9と10^9+7と回文 |
ユーザー |
![]() |
提出日時 | 2019-06-28 19:37:09 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,910 bytes |
コンパイル時間 | 2,397 ms |
コンパイル使用メモリ | 79,192 KB |
実行使用メモリ | 50,896 KB |
最終ジャッジ日時 | 2024-07-02 04:16:07 |
合計ジャッジ時間 | 8,858 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 WA * 2 |
ソースコード
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);}}