結果
問題 | No.856 増える演算 |
ユーザー | 37zigen |
提出日時 | 2019-07-27 10:59:51 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,271 ms / 3,153 ms |
コード長 | 3,625 bytes |
コンパイル時間 | 5,787 ms |
コンパイル使用メモリ | 75,544 KB |
実行使用メモリ | 104,560 KB |
最終ジャッジ日時 | 2023-09-15 06:10:39 |
合計ジャッジ時間 | 75,115 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 532 ms
88,096 KB |
testcase_01 | AC | 549 ms
88,260 KB |
testcase_02 | AC | 577 ms
87,872 KB |
testcase_03 | AC | 547 ms
88,028 KB |
testcase_04 | AC | 563 ms
87,776 KB |
testcase_05 | AC | 540 ms
88,052 KB |
testcase_06 | AC | 590 ms
87,712 KB |
testcase_07 | AC | 550 ms
87,808 KB |
testcase_08 | AC | 554 ms
88,052 KB |
testcase_09 | AC | 564 ms
87,696 KB |
testcase_10 | AC | 544 ms
88,052 KB |
testcase_11 | AC | 553 ms
87,660 KB |
testcase_12 | AC | 552 ms
87,484 KB |
testcase_13 | AC | 591 ms
88,100 KB |
testcase_14 | AC | 566 ms
87,980 KB |
testcase_15 | AC | 589 ms
87,832 KB |
testcase_16 | AC | 579 ms
87,636 KB |
testcase_17 | AC | 545 ms
87,972 KB |
testcase_18 | AC | 544 ms
87,732 KB |
testcase_19 | AC | 574 ms
88,252 KB |
testcase_20 | AC | 569 ms
87,768 KB |
testcase_21 | AC | 590 ms
89,616 KB |
testcase_22 | AC | 571 ms
87,840 KB |
testcase_23 | AC | 669 ms
86,048 KB |
testcase_24 | AC | 693 ms
87,792 KB |
testcase_25 | AC | 669 ms
86,168 KB |
testcase_26 | AC | 626 ms
88,248 KB |
testcase_27 | AC | 604 ms
87,880 KB |
testcase_28 | AC | 652 ms
86,540 KB |
testcase_29 | AC | 699 ms
97,752 KB |
testcase_30 | AC | 711 ms
97,948 KB |
testcase_31 | AC | 728 ms
91,660 KB |
testcase_32 | AC | 662 ms
91,656 KB |
testcase_33 | AC | 701 ms
85,028 KB |
testcase_34 | AC | 840 ms
90,304 KB |
testcase_35 | AC | 824 ms
91,332 KB |
testcase_36 | AC | 894 ms
92,484 KB |
testcase_37 | AC | 833 ms
86,536 KB |
testcase_38 | AC | 678 ms
86,740 KB |
testcase_39 | AC | 722 ms
97,524 KB |
testcase_40 | AC | 769 ms
96,200 KB |
testcase_41 | AC | 846 ms
91,988 KB |
testcase_42 | AC | 890 ms
92,148 KB |
testcase_43 | AC | 775 ms
97,976 KB |
testcase_44 | AC | 582 ms
88,496 KB |
testcase_45 | AC | 697 ms
97,532 KB |
testcase_46 | AC | 704 ms
85,984 KB |
testcase_47 | AC | 762 ms
97,656 KB |
testcase_48 | AC | 790 ms
90,404 KB |
testcase_49 | AC | 775 ms
91,672 KB |
testcase_50 | AC | 757 ms
85,936 KB |
testcase_51 | AC | 885 ms
91,844 KB |
testcase_52 | AC | 938 ms
88,764 KB |
testcase_53 | AC | 1,115 ms
90,496 KB |
testcase_54 | AC | 799 ms
91,508 KB |
testcase_55 | AC | 1,168 ms
95,688 KB |
testcase_56 | AC | 746 ms
86,408 KB |
testcase_57 | AC | 1,152 ms
96,032 KB |
testcase_58 | AC | 983 ms
97,648 KB |
testcase_59 | AC | 1,246 ms
96,380 KB |
testcase_60 | AC | 950 ms
90,272 KB |
testcase_61 | AC | 1,251 ms
104,560 KB |
testcase_62 | AC | 1,148 ms
101,848 KB |
testcase_63 | AC | 600 ms
85,388 KB |
testcase_64 | AC | 1,177 ms
101,488 KB |
testcase_65 | AC | 734 ms
86,124 KB |
testcase_66 | AC | 855 ms
97,732 KB |
testcase_67 | AC | 1,037 ms
94,556 KB |
testcase_68 | AC | 1,158 ms
96,364 KB |
testcase_69 | AC | 1,090 ms
103,824 KB |
testcase_70 | AC | 1,131 ms
98,824 KB |
testcase_71 | AC | 1,117 ms
99,624 KB |
testcase_72 | AC | 1,087 ms
95,584 KB |
testcase_73 | AC | 1,237 ms
96,252 KB |
testcase_74 | AC | 1,205 ms
96,548 KB |
testcase_75 | AC | 1,206 ms
95,776 KB |
testcase_76 | AC | 1,208 ms
96,588 KB |
testcase_77 | AC | 1,252 ms
95,956 KB |
testcase_78 | AC | 1,216 ms
96,572 KB |
testcase_79 | AC | 1,271 ms
96,104 KB |
testcase_80 | AC | 1,214 ms
97,100 KB |
testcase_81 | AC | 1,153 ms
96,348 KB |
testcase_82 | AC | 1,242 ms
96,776 KB |
ソースコード
import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; class Main { public static void main(String[] args) { new Main().run(); } final long MOD = (long) 1e9 + 7; long inv(long a) { return pow(a, MOD - 2); } long pow(long a, long n) { long ret = 1; for (; n > 0; n >>= 1, a = a * a % MOD) { if (n % 2 == 1) { ret = ret * a % MOD; } } return ret; } void run() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] A = new int[N]; for (int i = 0; i < N; ++i) { A[i] = sc.nextInt(); } long ans = 1; long sum = A[N - 1]; for (int i = N - 2; i >= 0; --i) { ans = ans * pow(A[i], sum) % MOD; sum += A[i]; sum %= MOD - 1; } long[] cnt = new long[100000 + 1]; for (int i = 0; i < N; ++i) cnt[A[i]]++; long[] cnt2 = mul(cnt, cnt); for (int i = 0; i < N; ++i) { cnt2[2 * A[i]]--; } for (int i = 0; i < cnt2.length; ++i) { cnt2[i] /= 2; ans = ans * pow(i, cnt2[i]) % MOD; } long coe = -1; double v = Double.MAX_VALUE / 3; long min = A[0]; for (int i = 1; i < N; ++i) { if (v > Math.log(A[i] + min) + A[i] * Math.log(min)) { v = Math.log(A[i] + min) + A[i] * Math.log(min); coe = (A[i] + min) % MOD * pow(min, A[i]) % MOD; } min = Math.min(min, A[i]); } ans = ans * inv(coe) % MOD; System.out.println(ans); } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } static long[] mul(long[] a, long[] b) { int n = 1; while (n < a.length + b.length) n *= 2; Complex[] ac = new Complex[n]; Complex[] bc = new Complex[n]; for (int i = 0; i < n; ++i) { ac[i] = new Complex(0, 0); bc[i] = new Complex(0, 0); } for (int i = 0; i < a.length; ++i) { ac[i].re = a[i]; } for (int i = 0; i < b.length; ++i) { bc[i].re = b[i]; } ac = fft(ac, false); bc = fft(bc, false); for (int i = 0; i < ac.length; ++i) { ac[i] = ac[i].mul(bc[i]); } ac = fft(ac, true); for (int i = 0; i < ac.length; ++i) { ac[i].re /= n; ac[i].co /= n; } long[] ret = new long[ac.length]; for (int i = 0; i < ret.length; ++i) { ret[i] = (long) Math.round(ac[i].re); } return ret; } static Complex[] fft(Complex[] a, boolean rev) { int n = a.length; if (n == 1) return a; int c = 0; for (int i = 1; i < n; ++i) { int j; for (j = n >> 1; j > (c ^= j); j >>= 1) ; if (c > i) { Complex tmp = a[c]; a[c] = a[i]; a[i] = tmp; } } for (int d = 1; d < n; d <<= 1) { for (int j = 0; j < d; ++j) { double angle = 2 * Math.PI / (2 * d) * (rev ? -1 : 1) * j; Complex mul = new Complex(Math.cos(angle), Math.sin(angle)); for (int pos = 0; pos < n; pos += 2 * d) { double ure = a[pos + j].re; double uco = a[pos + j].co; double vre = a[pos + j + d].re * mul.re - a[pos + j + d].co * mul.co; double vco = a[pos + j + d].co * mul.re + a[pos + j + d].re * mul.co; a[pos + j].re = ure + vre; a[pos + j].co = uco + vco; a[pos + j + d].re = ure - vre; a[pos + j + d].co = uco - vco; } } } return a; } Complex exp(double a) { return new Complex(Math.cos(a), Math.sin(a)); } static class Complex { double re, co; public Complex(double re, double co) { this.re = re; this.co = co; } Complex add(Complex o) { return new Complex(re + o.re, co + o.co); } Complex subtract(Complex o) { return new Complex(re - o.re, co - o.co); } Complex mul(Complex o) { return new Complex(re * o.re - co * o.co, re * o.co + o.re * co); } } }