結果
| 問題 | No.856 増える演算 |
| ユーザー |
 37zigen
|
| 提出日時 | 2019-07-27 10:35:11 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 3,605 bytes |
| コンパイル時間 | 2,329 ms |
| コンパイル使用メモリ | 77,872 KB |
| 実行使用メモリ | 109,312 KB |
| 最終ジャッジ日時 | 2023-09-15 06:07:04 |
| 合計ジャッジ時間 | 74,010 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 542 ms
88,176 KB |
| testcase_01 | AC | 576 ms
88,184 KB |
| testcase_02 | AC | 550 ms
88,324 KB |
| testcase_03 | AC | 576 ms
88,268 KB |
| testcase_04 | AC | 598 ms
88,548 KB |
| testcase_05 | AC | 549 ms
88,320 KB |
| testcase_06 | AC | 563 ms
87,972 KB |
| testcase_07 | AC | 565 ms
88,508 KB |
| testcase_08 | AC | 558 ms
88,572 KB |
| testcase_09 | AC | 538 ms
88,240 KB |
| testcase_10 | AC | 546 ms
86,376 KB |
| testcase_11 | AC | 536 ms
88,152 KB |
| testcase_12 | AC | 531 ms
88,596 KB |
| testcase_13 | AC | 571 ms
88,184 KB |
| testcase_14 | AC | 538 ms
87,912 KB |
| testcase_15 | AC | 566 ms
88,284 KB |
| testcase_16 | AC | 546 ms
88,212 KB |
| testcase_17 | AC | 542 ms
88,160 KB |
| testcase_18 | AC | 527 ms
88,260 KB |
| testcase_19 | AC | 536 ms
88,128 KB |
| testcase_20 | AC | 545 ms
87,952 KB |
| testcase_21 | AC | 535 ms
87,920 KB |
| testcase_22 | AC | 537 ms
88,548 KB |
| testcase_23 | AC | 605 ms
86,040 KB |
| testcase_24 | AC | 710 ms
86,092 KB |
| testcase_25 | AC | 684 ms
84,012 KB |
| testcase_26 | AC | 586 ms
87,936 KB |
| testcase_27 | AC | 597 ms
87,760 KB |
| testcase_28 | AC | 708 ms
86,048 KB |
| testcase_29 | AC | 707 ms
97,160 KB |
| testcase_30 | AC | 678 ms
96,944 KB |
| testcase_31 | AC | 683 ms
91,428 KB |
| testcase_32 | AC | 726 ms
85,328 KB |
| testcase_33 | AC | 776 ms
91,236 KB |
| testcase_34 | AC | 855 ms
86,108 KB |
| testcase_35 | AC | 810 ms
90,776 KB |
| testcase_36 | AC | 780 ms
85,924 KB |
| testcase_37 | AC | 802 ms
84,404 KB |
| testcase_38 | AC | 563 ms
84,384 KB |
| testcase_39 | AC | 734 ms
96,880 KB |
| testcase_40 | AC | 705 ms
85,676 KB |
| testcase_41 | AC | 814 ms
96,844 KB |
| testcase_42 | AC | 819 ms
85,940 KB |
| testcase_43 | AC | 755 ms
96,720 KB |
| testcase_44 | AC | 583 ms
88,240 KB |
| testcase_45 | AC | 747 ms
95,496 KB |
| testcase_46 | AC | 785 ms
91,692 KB |
| testcase_47 | AC | 762 ms
83,604 KB |
| testcase_48 | AC | 717 ms
85,444 KB |
| testcase_49 | AC | 736 ms
90,920 KB |
| testcase_50 | AC | 768 ms
96,780 KB |
| testcase_51 | AC | 868 ms
91,228 KB |
| testcase_52 | AC | 873 ms
90,284 KB |
| testcase_53 | AC | 1,110 ms
87,748 KB |
| testcase_54 | AC | 807 ms
91,080 KB |
| testcase_55 | AC | 1,120 ms
92,340 KB |
| testcase_56 | AC | 784 ms
83,660 KB |
| testcase_57 | AC | 1,139 ms
94,924 KB |
| testcase_58 | AC | 940 ms
89,596 KB |
| testcase_59 | AC | 1,228 ms
96,068 KB |
| testcase_60 | AC | 930 ms
95,520 KB |
| testcase_61 | AC | 1,245 ms
101,376 KB |
| testcase_62 | AC | 1,146 ms
101,860 KB |
| testcase_63 | AC | 698 ms
87,384 KB |
| testcase_64 | AC | 1,138 ms
91,588 KB |
| testcase_65 | AC | 724 ms
84,428 KB |
| testcase_66 | AC | 836 ms
85,408 KB |
| testcase_67 | AC | 1,050 ms
100,916 KB |
| testcase_68 | AC | 1,172 ms
88,248 KB |
| testcase_69 | AC | 1,224 ms
101,500 KB |
| testcase_70 | AC | 1,188 ms
96,316 KB |
| testcase_71 | AC | 1,149 ms
101,652 KB |
| testcase_72 | AC | 1,199 ms
101,616 KB |
| testcase_73 | AC | 1,279 ms
95,312 KB |
| testcase_74 | AC | 1,279 ms
95,724 KB |
| testcase_75 | AC | 1,203 ms
95,628 KB |
| testcase_76 | AC | 1,215 ms
95,576 KB |
| testcase_77 | AC | 1,229 ms
92,916 KB |
| testcase_78 | AC | 1,254 ms
96,844 KB |
| testcase_79 | AC | 1,256 ms
95,476 KB |
| testcase_80 | AC | 1,264 ms
95,500 KB |
| testcase_81 | AC | 1,260 ms
95,532 KB |
| testcase_82 | WA | - |
ソースコード
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;
int[] cnt = new int[100000 + 1];
for (int i = 0; i < N; ++i)
cnt[A[i]]++;
int[] 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) * 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 int[] mul(int[] a, int[] 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;
}
int[] ret = new int[ac.length];
for (int i = 0; i < ret.length; ++i) {
ret[i] = (int) 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);
}
}
}