結果

問題 No.856 増える演算
ユーザー 37zigen37zigen
提出日時 2019-07-27 10:14:30
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 3,448 bytes
コンパイル時間 2,421 ms
コンパイル使用メモリ 75,572 KB
実行使用メモリ 104,068 KB
最終ジャッジ日時 2023-09-15 06:04:07
合計ジャッジ時間 79,583 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 521 ms
87,036 KB
testcase_01 AC 538 ms
88,208 KB
testcase_02 AC 615 ms
88,004 KB
testcase_03 WA -
testcase_04 AC 557 ms
88,396 KB
testcase_05 AC 563 ms
88,188 KB
testcase_06 WA -
testcase_07 AC 560 ms
88,424 KB
testcase_08 AC 543 ms
88,516 KB
testcase_09 AC 535 ms
88,524 KB
testcase_10 AC 553 ms
88,356 KB
testcase_11 AC 531 ms
88,120 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 560 ms
88,292 KB
testcase_20 AC 579 ms
88,656 KB
testcase_21 AC 616 ms
88,352 KB
testcase_22 AC 584 ms
88,224 KB
testcase_23 AC 637 ms
85,528 KB
testcase_24 AC 719 ms
97,312 KB
testcase_25 AC 695 ms
91,244 KB
testcase_26 AC 575 ms
88,236 KB
testcase_27 AC 576 ms
88,060 KB
testcase_28 AC 638 ms
86,008 KB
testcase_29 AC 756 ms
97,020 KB
testcase_30 AC 713 ms
96,884 KB
testcase_31 AC 694 ms
91,064 KB
testcase_32 AC 678 ms
85,456 KB
testcase_33 AC 887 ms
86,036 KB
testcase_34 AC 1,081 ms
91,616 KB
testcase_35 AC 895 ms
91,368 KB
testcase_36 AC 873 ms
87,676 KB
testcase_37 AC 915 ms
85,232 KB
testcase_38 AC 561 ms
84,572 KB
testcase_39 AC 663 ms
97,032 KB
testcase_40 AC 766 ms
97,504 KB
testcase_41 AC 779 ms
89,608 KB
testcase_42 AC 902 ms
87,424 KB
testcase_43 AC 835 ms
98,156 KB
testcase_44 AC 538 ms
88,384 KB
testcase_45 AC 747 ms
98,008 KB
testcase_46 AC 833 ms
87,160 KB
testcase_47 AC 654 ms
83,848 KB
testcase_48 AC 817 ms
86,956 KB
testcase_49 AC 943 ms
91,152 KB
testcase_50 AC 1,015 ms
98,524 KB
testcase_51 AC 966 ms
91,032 KB
testcase_52 AC 1,012 ms
91,280 KB
testcase_53 WA -
testcase_54 AC 952 ms
91,200 KB
testcase_55 WA -
testcase_56 AC 864 ms
85,788 KB
testcase_57 AC 1,206 ms
95,580 KB
testcase_58 AC 1,099 ms
92,032 KB
testcase_59 AC 1,287 ms
96,792 KB
testcase_60 WA -
testcase_61 AC 1,338 ms
102,364 KB
testcase_62 AC 1,300 ms
102,436 KB
testcase_63 AC 590 ms
95,928 KB
testcase_64 AC 1,257 ms
90,936 KB
testcase_65 WA -
testcase_66 AC 995 ms
87,112 KB
testcase_67 WA -
testcase_68 AC 1,318 ms
96,636 KB
testcase_69 AC 1,252 ms
102,036 KB
testcase_70 AC 1,442 ms
96,016 KB
testcase_71 AC 1,287 ms
102,352 KB
testcase_72 WA -
testcase_73 AC 1,359 ms
96,804 KB
testcase_74 AC 1,522 ms
96,860 KB
testcase_75 WA -
testcase_76 AC 1,317 ms
96,228 KB
testcase_77 AC 1,472 ms
97,436 KB
testcase_78 WA -
testcase_79 AC 1,361 ms
96,396 KB
testcase_80 AC 1,452 ms
96,724 KB
testcase_81 AC 1,427 ms
95,932 KB
testcase_82 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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;
		}
		
		Arrays.sort(A);
		if (A[0] <= 2)
			ans = ans * inv((A[0] + A[1]) * pow(A[0], A[1]) % MOD) % MOD;
		else
			ans = ans * inv((A[0] + A[1]) * pow(A[1], A[0]) % MOD) % 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);
		}
	}
}
0