結果

問題 No.856 増える演算
コンテスト
ユーザー CuriousFairy315
提出日時 2019-03-17 18:24:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,950 bytes
コンパイル時間 604 ms
コンパイル使用メモリ 82,288 KB
最終ジャッジ日時 2025-01-06 22:33:17
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdint>
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<int, int> 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)となる
*/
0