結果
| 問題 | No.856 増える演算 |
| ユーザー |
 kimiyuki
|
| 提出日時 | 2020-08-11 19:48:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,418 bytes |
| コンパイル時間 | 3,351 ms |
| コンパイル使用メモリ | 206,240 KB |
| 最終ジャッジ日時 | 2025-01-12 20:24:28 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 3 WA * 42 RE * 3 TLE * 32 |
ソースコード
#line 1 "main.cpp"#include <bits/stdc++.h>#line 2 "/home/user/Library/utils/macros.hpp"#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))#define ALL(x) std::begin(x), std::end(x)#line 4 "/home/user/Library/modulus/modpow.hpp"inline int32_t modpow(uint_fast64_t x, uint64_t k, int32_t MOD) {assert (/* 0 <= x and */ x < (uint_fast64_t)MOD);uint_fast64_t y = 1;for (; k; k >>= 1) {if (k & 1) (y *= x) %= MOD;(x *= x) %= MOD;}assert (/* 0 <= y and */ y < (uint_fast64_t)MOD);return y;}#line 5 "/home/user/Library/modulus/modinv.hpp"inline int32_t modinv_nocheck(int32_t value, int32_t MOD) {assert (0 <= value and value < MOD);if (value == 0) return -1;int64_t a = value, b = MOD;int64_t x = 0, y = 1;for (int64_t u = 1, v = 0; a; ) {int64_t q = b / a;x -= q * u; std::swap(x, u);y -= q * v; std::swap(y, v);b -= q * a; std::swap(b, a);}if (not (value * x + MOD * y == b and b == 1)) return -1;if (x < 0) x += MOD;assert (0 <= x and x < MOD);return x;}inline int32_t modinv(int32_t x, int32_t MOD) {int32_t y = modinv_nocheck(x, MOD);assert (y != -1);return y;}#line 6 "/home/user/Library/modulus/mint.hpp"/*** @brief quotient ring / 剰余環 $\mathbb{Z}/n\mathbb{Z}$*/template <int32_t MOD>struct mint {int32_t value;mint() : value() {}mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {}mint(int32_t value_, std::nullptr_t) : value(value_) {}explicit operator bool() const { return value; }inline mint<MOD> operator + (mint<MOD> other) const { return mint<MOD>(*this) += other; }inline mint<MOD> operator - (mint<MOD> other) const { return mint<MOD>(*this) -= other; }inline mint<MOD> operator * (mint<MOD> other) const { return mint<MOD>(*this) *= other; }inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }inline mint<MOD> & operator -= (mint<MOD> other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; }inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; }inline mint<MOD> operator - () const { return mint<MOD>(this->value ? MOD - this->value : 0, nullptr); }inline bool operator == (mint<MOD> other) const { return value == other.value; }inline bool operator != (mint<MOD> other) const { return value != other.value; }inline mint<MOD> pow(uint64_t k) const { return mint<MOD>(modpow(value, k, MOD), nullptr); }inline mint<MOD> inv() const { return mint<MOD>(modinv(value, MOD), nullptr); }inline mint<MOD> operator / (mint<MOD> other) const { return *this * other.inv(); }inline mint<MOD> & operator /= (mint<MOD> other) { return *this *= other.inv(); }};template <int32_t MOD> mint<MOD> operator + (int64_t value, mint<MOD> n) { return mint<MOD>(value) + n; }template <int32_t MOD> mint<MOD> operator - (int64_t value, mint<MOD> n) { return mint<MOD>(value) - n; }template <int32_t MOD> mint<MOD> operator * (int64_t value, mint<MOD> n) { return mint<MOD>(value) * n; }template <int32_t MOD> mint<MOD> operator / (int64_t value, mint<MOD> n) { return mint<MOD>(value) / n; }template <int32_t MOD> std::istream & operator >> (std::istream & in, mint<MOD> & n) { int64_t value; in >> value; n = value; return in; }template <int32_t MOD> std::ostream & operator << (std::ostream & out, mint<MOD> n) { return out << n.value; }#line 5 "/home/user/Library/number/karatsuba.hpp"/*** @brief Karatsuba method ($O(n^{\log_2 3})$)*/template <class CommutativeRing>std::vector<CommutativeRing> karatsuba_convolution(const std::vector<CommutativeRing> & x, const std::vector<CommutativeRing> & y) {int n = x.size();int m = y.size();if ((int64_t)n * m <= 100) {std::vector<CommutativeRing> z(n + m - 1);REP (i, n) REP (j, m) {z[i + j] += x[i] * y[j];}return z;}int half = (std::max(n, m) + 1) / 2;std::vector<CommutativeRing> x0(x.begin(), x.begin() + std::min(n, half));std::vector<CommutativeRing> y0(y.begin(), y.begin() + std::min(m, half));std::vector<CommutativeRing> z0 = karatsuba_convolution(x0, y0);std::vector<CommutativeRing> x1(x.begin() + std::min(n, half), x.end());std::vector<CommutativeRing> y1(y.begin() + std::min(m, half), y.end());std::vector<CommutativeRing> z2 = karatsuba_convolution(x1, y1);assert (x1.size() <= x0.size());std::vector<CommutativeRing> dx = x0;REP (i, x1.size()) dx[i] -= x1[i];assert (y1.size() <= y0.size());std::vector<CommutativeRing> dy = y0;REP (i, y1.size()) dy[i] -= y1[i];std::vector<CommutativeRing> dz = karatsuba_convolution(dx, dy);std::vector<CommutativeRing> z(n + m - 1);REP (i, z0.size()) {z[i] += z0[i];if (half + i < (int)z.size()) z[half + i] += z0[i];}REP (i, dz.size()) {if (half + i < (int)z.size()) z[half + i] -= dz[i];}REP (i, z2.size()) {z[half + i] += z2[i];if (2 * half + i < (int)z.size()) z[2 * half + i] += z2[i];}return z;}#line 5 "main.cpp"using namespace std;template <class CommutativeRing>std::vector<CommutativeRing> karatsuba_special_convolution(const std::vector<CommutativeRing> & x) {int n = x.size();if ((int64_t)n * n <= 100) {std::vector<CommutativeRing> z(2 * n - 1);REP (i, n) REP3 (j, i + 1, n) {z[i + j] += x[i] * x[j];}return z;}int half = (n + 1) / 2;std::vector<CommutativeRing> x0(x.begin(), x.begin() + std::min(n, half));std::vector<CommutativeRing> x1(x.begin() + std::min(n, half), x.end());std::vector<CommutativeRing> z0 = karatsuba_special_convolution(x0);std::vector<CommutativeRing> z1 = karatsuba_convolution(x0, x1);std::vector<CommutativeRing> z2 = karatsuba_special_convolution(x1);std::vector<CommutativeRing> z(2 * n - 1);REP (i, z0.size()) {z[i] += z0[i];if (half + i < (int)z.size()) z[half + i] += z0[i];}REP (i, z1.size()) {if (half + i < (int)z.size()) z[half + i] += z1[i];}REP (i, z2.size()) {if (2 * half + i < (int)z.size()) z[2 * half + i] += z2[i];}return z;}constexpr int64_t MOD = 1000000007;// the commutative ring (F, *, +) for the finite field (F, +, *)struct cring_t {mint<MOD> value;cring_t() : value(1) {}};cring_t & operator += (cring_t & a, cring_t b) {a.value *= b.value; return a;}cring_t & operator -= (cring_t & a, cring_t b) {a.value /= b.value; return a;}cring_t & operator *= (cring_t & a, cring_t b) {a.value += b.value; return a;}cring_t operator + (cring_t a, cring_t b) {return a += b;}cring_t operator - (cring_t a, cring_t b) {return a -= b;}cring_t operator * (cring_t a, cring_t b) {return a *= b;}mint<MOD> solve(int n, const vector<int64_t> &a) {mint<MOD> x = 1;{vector<cring_t> b(n);REP (i, n) {b[i].value = a[i];}auto c = karatsuba_special_convolution<cring_t>(b);for (auto c_i : c) {x *= c_i.value;}}mint<MOD> y = 1;{int64_t sum_a_j = 0;REP_R (i, n) {y *= mint<MOD>(a[i]).pow(sum_a_j);sum_a_j += a[i];}}mint<MOD> z = 0;{double log_z = INFINITY;int64_t a_j = a[n - 1];REP_R (i, n - 1) {double log_a_i_a_j = log(a[i] + a_j) + a_j * log(a[i]);if (log_a_i_a_j < log_z) {log_z = log_a_i_a_j;z = mint<MOD>(a[i] + a_j) * mint<MOD>(a[i]).pow(a_j);}a_j = min(a[i], a_j);}}return x * y / z;}int main() {int n; cin >> n;vector<int64_t> a(n);REP (i, n) {cin >> a[i];}auto ans = solve(n, a);cout << ans << endl;return 0;}