#include #include #include #include using namespace std; // 575 const int MAX = 100000; const int MAX2 = 1000; const int MOD = 1000000007; // 今回使う余り int64_t pow(int64_t n, int m, int mod) { if (m == 0) return 1; if (m == 1) return n; if (m == 2) return n * n % mod; return pow(pow(n, m / 2, mod), 2, mod) * pow(n, m & 1, mod) % mod; } int main() { int N; static int A[MAX]; cin >> N; if (N < 2 || N > MAX) { cout << "No Judge"; return 0; } for (int i = 0;i < N;++ i) { cin >> A[i]; if (A[i] < 1 || A[i] > MAX2) { cout << "No Judge"; return 0; } } int count[MAX2 + 1], add[2 * MAX2 + 1], sum = 0; static double mini = log(A[0] + A[1]) + A[1] * log(A[0]); static pair minimum = make_pair(A[0], A[1]); int64_t ans = 1; for (int i = 0;i <= MAX2;++ i) count[i] = 0; for (int i = 0;i <= 2 * MAX2;++ i) add[i] = 0; for (int i = 0;i < N;++ i) { ++ count[A[i]]; // バケット sum += A[i]; } for (int i = 0, j = 0;i < N;++ i) { -- count[A[i]]; sum -= A[i]; while (!count[j]) ++ j; if (mini > log(A[i] + j) + j * log(A[i])) { mini = log(A[i] + j) + j * log(A[i]); minimum = make_pair(A[i], j); } for (int k = j;k <= MAX2;++ k) add[A[i] + k] += count[k]; ans = ans * pow(A[i], sum, MOD) % MOD; } for (int i = 0;i < 2 * MAX2 + 1;++ i) if (add[i]) ans = ans * pow(i, add[i], MOD) % MOD; ans = ans * pow(minimum.first + minimum.second, MOD - 2, MOD) % MOD * pow(pow(minimum.first, minimum.second, MOD), MOD - 2, MOD) % MOD; cout << ans << endl; return 0; } /* 31536000のコメント解説欄 ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー まず、とっとと最小の要素を特定してしまうことを考える 指数が厄介なので、先にiの方を固定する この時、jはiより大きい値の中でA_j最小であることは自明であるから、セグメント木などを使うとO(logN)で候補を取り出せる これを各iについてやると全部でN個の候補ができて、その中で最小のものは実際に比較すれば良い これらの操作により、O(N(logN+logA))で最小の値が求まる 次に、全ての積を求める また、iを固定して考えていく 各iについて、和に関してはA_jの値の範囲が狭いことからバケットソートをすればO(A)で求めることができ、 指数に関しては積上では和の計算に等しいからsum(A_j)をすればよくて、これは前もって計算しておけば良い これによって、O(A(N+logA))で全ての積が求まった 後は割る操作に関してはフェルマーの定理でも使えばいいし、使わなくても答えは求まる 最終的に、計算量はO(NA+NlogN+(N+A)logA)となる */