結果
問題 | No.1334 Multiply or Add |
ユーザー |
![]() |
提出日時 | 2021-01-08 23:21:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 7,755 bytes |
コンパイル時間 | 1,095 ms |
コンパイル使用メモリ | 84,400 KB |
最終ジャッジ日時 | 2025-01-17 14:40:14 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 71 |
ソースコード
#line 1 "main.cpp"/*** @title Template*/#include <iostream>#include <algorithm>#include <utility>#include <numeric>#include <vector>#include <array>#include <cassert>#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"class range {struct iter {std::size_t itr;constexpr iter(std::size_t pos) noexcept: itr(pos) { }constexpr void operator ++ () noexcept { ++itr; }constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }constexpr std::size_t operator * () const noexcept { return itr; }};struct reviter {std::size_t itr;constexpr reviter(std::size_t pos) noexcept: itr(pos) { }constexpr void operator ++ () noexcept { --itr; }constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }constexpr std::size_t operator * () const noexcept { return itr; }};const iter first, last;public:constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }constexpr iter begin() const noexcept { return first; }constexpr iter end() const noexcept { return last; }constexpr reviter rbegin() const noexcept { return reviter(*last - 1); }constexpr reviter rend() const noexcept { return reviter(*first - 1); }};/*** @title Range*/#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/modular.cpp"#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/mod_inv.cpp"#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/mod_inv.cpp"#include <cstdint>constexpr std::pair<int64_t, int64_t> mod_inv(int64_t a, int64_t b) {if ((a %= b) == 0) return { b, 0 };int64_t s = b, t = (a < 0 ? a + b : a);int64_t m0 = 0, m1 = 1, tmp = 0;while (t > 0) {const auto u = s / t;s -= t * u; m0 -= m1 * u;tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp;}return { s, (m0 < 0 ? m0 + b / s : m0) };}/*** @title Extended GCD*/#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/modular.cpp"#line 8 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/modular.cpp"#include <type_traits>template <class Modulus>class modular {public:using value_type = uint32_t;using cover_type = uint64_t;static constexpr uint32_t mod() { return Modulus::mod(); }template <class T>static constexpr value_type normalize(T value_) noexcept {if (value_ < 0) {value_ = -value_;value_ %= mod();if (value_ == 0) return 0;return mod() - value_;}return value_ % mod();}private:value_type value;template <bool IsPrime, std::enable_if_t<IsPrime>* = nullptr>constexpr modular inverse_helper() const noexcept { return power(*this, mod() - 2); }template <bool IsPrime, std::enable_if_t<!IsPrime>* = nullptr>constexpr modular inverse_helper() const noexcept {const auto tmp = mod_inv(value, mod());assert(tmp.first == 1);return modular(tmp.second);}public:constexpr modular() noexcept : value(0) { }template <class T>explicit constexpr modular(T value_) noexcept : value(normalize(value_)) { }template <class T>explicit constexpr operator T() const noexcept { return static_cast<T>(value); }constexpr value_type get() const noexcept { return value; }constexpr value_type &extract() noexcept { return value; }constexpr modular operator - () const noexcept { return modular(mod() - value); }constexpr modular operator ~ () const noexcept { return inverse(*this); }constexpr modular operator + (const modular &rhs) const noexcept { return modular(*this) += rhs; }constexpr modular& operator += (const modular &rhs) noexcept {if ((value += rhs.value) >= mod()) value -= mod();return *this;}constexpr modular operator - (const modular &rhs) const noexcept { return modular(*this) -= rhs; }constexpr modular& operator -= (const modular &rhs) noexcept {if ((value += mod() - rhs.value) >= mod()) value -= mod();return *this;}constexpr modular operator * (const modular &rhs) const noexcept { return modular(*this) *= rhs; }constexpr modular& operator *= (const modular &rhs) noexcept {value = (cover_type) value * rhs.value % mod();return *this;}constexpr modular operator / (const modular &rhs) const noexcept { return modular(*this) /= rhs; }constexpr modular& operator /= (const modular &rhs) noexcept { return (*this) *= inverse(rhs); }constexpr bool zero() const noexcept { return value == 0; }constexpr bool operator == (const modular &rhs) const noexcept { return value == rhs.value; }constexpr bool operator != (const modular &rhs) const noexcept { return value != rhs.value; }friend std::ostream& operator << (std::ostream &stream, const modular &rhs) { return stream << rhs.value; }friend constexpr modular inverse(const modular &val) noexcept { return val.inverse_helper<Modulus::is_prime>(); }friend constexpr modular power(modular val, cover_type exp) noexcept {modular res(1);for (; exp > 0; exp >>= 1, val *= val) if (exp & 1) res *= val;return res;}};template <uint32_t Mod, bool IsPrime = true>struct static_modulus {static constexpr uint32_t mod() noexcept { return Mod; }static constexpr bool is_prime = IsPrime;};template <uint32_t Id = 0, bool IsPrime = false>struct dynamic_modulus {static uint32_t &mod() noexcept { static uint32_t val = 0; return val; }static constexpr bool is_prime = IsPrime;};template <uint32_t Mod, bool IsPrime = true>using mint32_t = modular<static_modulus<Mod, IsPrime>>;using rmint32_t = modular<dynamic_modulus<>>;/** @title Modint*/#line 16 "main.cpp"using i32 = std::int32_t;using i64 = std::int64_t;using u32 = std::uint32_t;using u64 = std::uint64_t;using isize = std::ptrdiff_t;using usize = std::size_t;constexpr i32 inf32 = (u32) ~0 >> 2;constexpr i64 inf64 = (u64) ~0 >> 2;template <class T>using Vec = std::vector<T>;using Fp = mint32_t<1000000007>;int main() {usize N;std::cin >> N;Vec<u64> A(N);for (auto &x: A) {std::cin >> x;}{u64 mul = 1;bool big = false;for (const auto x: A) {mul *= x;if (mul > (u64) 200005 * 200005) {big = true;break;}}if (big) {Fp prd(1), sum;usize l = 0;while (A[l] == 1) {l += 1;sum += Fp(1);}usize r = N;while (A[r - 1] == 1) {r -= 1;sum += Fp(1);}for (auto i: range(l, r)) {prd *= Fp(A[i]);}std::cout << prd + sum << '\n';return 0;}}Fp ans;Vec<std::pair<u64, u64>> vec;{usize index = 0;while (index < N && A[index] == 1) {ans += Fp(1);index += 1;}while (index < N) {u64 mul = 1;while (index < N && A[index] != 1) {mul *= A[index];index += 1;}u64 sum = 0;while (index < N && A[index] == 1) {sum += 1;index += 1;}vec.emplace_back(mul, sum);}}const auto Size = vec.size();Vec<Vec<u64>> calc(Size, Vec<u64>(Size + 1));for (auto i: range(0, Size)) {for (auto j: range(i + 1, Size + 1)) {calc[i][j] = 1;for (auto k: range(i, j)) {calc[i][j] *= vec[k].first;}}}Vec<u64> dp(Size + 1);for (auto i: range(0, Size)) {for (auto j: range(i + 1, Size + 1)) {dp[j] = std::max(dp[j], dp[i] + calc[i][j] + vec[j - 1].second);}}std::cout << ans + Fp(dp.back()) << '\n';return 0;}