結果
問題 | No.1084 積の積 |
ユーザー |
![]() |
提出日時 | 2020-06-19 22:43:50 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 670 ms / 2,000 ms |
コード長 | 1,192 bytes |
コンパイル時間 | 2,038 ms |
コンパイル使用メモリ | 77,544 KB |
実行使用メモリ | 53,300 KB |
最終ジャッジ日時 | 2024-07-03 15:16:27 |
合計ジャッジ時間 | 16,562 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 27 |
ソースコード
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;}}