結果
問題 | No.1084 積の積 |
ユーザー | ks2m |
提出日時 | 2020-06-19 22:43:50 |
言語 | Java19 (openjdk 21) |
結果 |
AC
|
実行時間 | 773 ms / 2,000 ms |
コード長 | 1,192 bytes |
コンパイル時間 | 2,051 ms |
コンパイル使用メモリ | 74,448 KB |
実行使用メモリ | 71,444 KB |
最終ジャッジ日時 | 2023-09-16 14:59:39 |
合計ジャッジ時間 | 16,629 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 123 ms
55,768 KB |
testcase_01 | AC | 124 ms
56,040 KB |
testcase_02 | AC | 125 ms
55,816 KB |
testcase_03 | AC | 125 ms
55,956 KB |
testcase_04 | AC | 648 ms
65,112 KB |
testcase_05 | AC | 124 ms
56,092 KB |
testcase_06 | AC | 773 ms
71,444 KB |
testcase_07 | AC | 125 ms
55,740 KB |
testcase_08 | AC | 127 ms
55,496 KB |
testcase_09 | AC | 459 ms
60,576 KB |
testcase_10 | AC | 124 ms
55,844 KB |
testcase_11 | AC | 211 ms
58,184 KB |
testcase_12 | AC | 435 ms
60,796 KB |
testcase_13 | AC | 561 ms
60,436 KB |
testcase_14 | AC | 396 ms
60,668 KB |
testcase_15 | AC | 407 ms
60,700 KB |
testcase_16 | AC | 590 ms
61,048 KB |
testcase_17 | AC | 427 ms
60,836 KB |
testcase_18 | AC | 548 ms
60,856 KB |
testcase_19 | AC | 608 ms
60,676 KB |
testcase_20 | AC | 334 ms
60,292 KB |
testcase_21 | AC | 415 ms
60,384 KB |
testcase_22 | AC | 381 ms
60,708 KB |
testcase_23 | AC | 474 ms
60,492 KB |
testcase_24 | AC | 484 ms
60,684 KB |
testcase_25 | AC | 570 ms
60,404 KB |
testcase_26 | AC | 529 ms
62,892 KB |
testcase_27 | AC | 520 ms
60,472 KB |
testcase_28 | AC | 543 ms
60,616 KB |
testcase_29 | AC | 541 ms
60,368 KB |
testcase_30 | AC | 536 ms
60,980 KB |
testcase_31 | AC | 553 ms
60,404 KB |
ソースコード
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); if (a[i] == 0) { System.out.println(0); return; } } sc.close(); long[] cnt = new long[n]; long[] cnt2 = new long[n + 2]; long val = 1; int r = 0; for (int l = 0; l < n; l++) { while (r < n && val < 1000000000) { val *= a[r]; r++; } if (val >= 1000000000) { r--; } cnt[l] = r - l; cnt2[l + 1]++; cnt2[r + 1]--; if (r < n) { val /= a[r]; } val /= a[l]; } for (int i = 1; i < cnt2.length; i++) { cnt2[i] += cnt2[i - 1]; } for (int i = 1; i < cnt.length; i++) { cnt[i] += cnt[i - 1] - cnt2[i]; } long ans = 1; int mod = 1000000007; for (int i = 0; i < n; i++) { ans *= power(a[i], cnt[i], mod); ans %= mod; } System.out.println(ans); } static long power(long x, long n, int m) { if (n == 0) { return 1; } long val = power(x, n / 2, m); val = val * val % m; if (n % 2 == 1) { val = val * x % m; } return val; } }