結果
| 問題 | No.856 増える演算 |
| ユーザー |
 ianCK
|
| 提出日時 | 2020-01-01 03:28:51 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,200 bytes |
| コンパイル時間 | 601 ms |
| コンパイル使用メモリ | 47,488 KB |
| 実行使用メモリ | 20,656 KB |
| 最終ジャッジ日時 | 2024-05-01 03:28:56 |
| 合計ジャッジ時間 | 9,523 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:63:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
63 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
main.cpp:64:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
64 | for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
ソースコード
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;
typedef long long int ll;
constexpr int kMod = int(1E9 + 7), kN = 262144;
constexpr ll kkMod = 75161927681ll;
ll Pow(ll a, ll b, ll p = kMod) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
void Ntt(vector<__int128> &v, bool on, int sz) {
ll wn, u, t, w, inv;
for (int i = 1, j = sz >> 1, k; i < (sz - 1); i++) {
if (i < j) swap(v[i], v[j]);
k = sz >> 1;
while (j & k) {
j ^= k;
k >>= 1;
}
j |= k;
}
for (int i = 2; i <= sz; i <<= 1) {
wn = on ? Pow(3, (kkMod - 1) / i, kkMod) : Pow(3, kkMod - 1 - (kkMod - 1) / i, kkMod);
for (int j = 0; j < sz; j += i) {
w = 1;
for (int k = j; k < j + (i >> 1); k++) {
u = v[k];
t = (w * v[k + (i >> 1)]) % kkMod;
v[k] = (u + t) % kkMod;
v[k + (i >> 1)] = (u - t + kkMod) % kkMod;
w = (w * wn) % kkMod;
}
}
}
if (on) {
inv = Pow(sz, kkMod - 2, kkMod);
for (int i = 0; i < sz; i++) v[i] = v[i] * inv % kkMod;
}
}
int a[kN];
ll ts[kN];
bool Lesser(int ax, int ay, int bx, int by) {
long double left = (ax + ay), right = (bx + by);
left *= pow(ax, ay), right *= pow(bx, by);
return left > right;
}
int main() {
int n, l, r, nm;
ll ans = 1, tmp = 1;
vector<__int128> v(kN);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
ts[0] = 0;
for (int i = 1; i <= n; i++) ts[i] = (ts[i - 1] + a[i]) % (kMod - 1);
for (int i = 1; i <= n; i++) v[a[i]]++;
Ntt(v, false, kN);
for (int i = 0; i < kN; i++) v[i] = v[i] * v[i] % kkMod;
Ntt(v, true, kN);
for (int i = 1; i <= n; i++) v[a[i] << 1]--;
for (int i = 1; i < kN; i++) v[i] >>= 1;
for (int i = 1; i < kN; i++) tmp = tmp * Pow(i, v[i]) % kMod;
for (int i = 1; i <= n; i++) ans = ans * Pow(a[i], ts[n] - ts[i] + kMod - 1) % kMod;
l = a[n - 1], r = a[n], nm = a[n];
for (int i = n - 2; i >= 1; i--) {
nm = min(nm, a[i + 1]);
if (Lesser(l, r, a[i], nm)) {
l = a[i];
r = nm;
}
}
ans = ans * tmp % kMod;
printf("%lld\n", ans * Pow((l + r) * Pow(l, r) % kMod, kMod - 2) % kMod);
}