結果
| 問題 | No.1084 積の積 |
| ユーザー |
 Imperi_Night
|
| 提出日時 | 2020-06-19 21:59:59 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 159 ms / 2,000 ms |
| コード長 | 6,069 bytes |
| コンパイル時間 | 2,195 ms |
| コンパイル使用メモリ | 148,660 KB |
| 最終ジャッジ日時 | 2025-01-11 06:16:29 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 27 |
ソースコード
#line 1 "main.cpp"#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cctype>#include <cstdint>#include <cstdlib>#include <cmath>#include <complex>#include <chrono>#include <deque>#include <functional>#include <iomanip>#include <iostream>#include <map>#include <memory>#include <numeric>#include <queue>#include <set>#include <stack>#include <string>#include <unordered_map>#include <vector>#include <random>#include <utility>#include <limits>#include <list>#include <type_traits>/* template start */#define rep(i, a, b) for (long long i = (a); (i) < (b); (i)++)#define all(i) i.begin(), i.end()#ifdef LOCAL#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#else#define debug(...)#endifvoid debug_out(){std::cerr<<std::endl;}template<typename Head,typename... Tail>void debug_out(Head h,Tail... t){std::cerr<<" "<<h;if(sizeof...(t)>0)std::cout<<" :";debug_out(t...);}template <typename T1, typename T2>std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {return os << pa.first << " " << pa.second;}template <typename T>std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");return os;}template<typename T1,typename T2>inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}template<typename T1,typename T2>inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}template<typename Num>constexpr Num mypow(Num a, long long b) {if(b==0)return 1;if (a==0)return 0;Num x = 1;while (b > 0) {if(b & 1)x*=a;a*=a;b >>= 1;}return x;}/* template end */using ll = long long;#line 2 "/mnt/c/Users/Imperi/Documents/cp-library/lib/DisjointSparseTable.hpp"#line 5 "/mnt/c/Users/Imperi/Documents/cp-library/lib/DisjointSparseTable.hpp"template<typename Semigroup>class DisjointSparseTable{public:using value_t=typename Semigroup::value_t;using size_t=std::size_t;private:size_t n,n0;std::vector<size_t> ln;std::vector<std::vector<value_t>> table;public:DisjointSparseTable(const std::vector<value_t>& a):n(a.size()){n0=1;while(n0<n)n0<<=1;ln=std::vector<size_t>(n0+1,0);for(size_t i=1;i<n0+1;i++)ln[i]=ln[i-1]+(i>=(1ull<<(ln[i-1]+1)));table=std::vector<std::vector<value_t>>(ln[n0]+1,a);for(size_t i=1;i<ln[n0]+1;i++){for(long long j=1ll<<(i-1);j<n;j+=1ll<<i){for(long long k=j-2;k>=j-(1ll<<(i-1));k--)table[i][k]=Semigroup::op(a[k],table[i][k+1]);for(long long k=j+1;k<std::min(j+(1ll<<(i-1)),(long long)n);k++)table[i][k]=Semigroup::op(table[i][k-1],a[k]);}}}value_t fold(size_t l,size_t r){assert(0<=l&&l<r&&r<=n);if(r==l+1)return table[0][l];size_t m=ln[l^(r-1)];return Semigroup::op(table[m+1][l],table[m+1][r-1]);}};#line 2 "/mnt/c/Users/Imperi/Documents/cp-library/lib/local/modint.hpp"#line 4 "/mnt/c/Users/Imperi/Documents/cp-library/lib/local/modint.hpp"template <std::uint_fast64_t Modulus> class modint {using u64 = std::uint_fast64_t;public:u64 a;constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}constexpr u64 &value() noexcept { return a; }constexpr const u64 &value() const noexcept { return a; }constexpr bool operator==(const modint rhs) const noexcept {return a==rhs.a;}constexpr bool operator!=(const modint rhs) const noexcept {return !(*this==rhs);}constexpr modint operator+(const modint rhs) const noexcept {return modint(*this) += rhs;}constexpr modint operator-(const modint rhs) const noexcept {return modint(*this) -= rhs;}constexpr modint operator*(const modint rhs) const noexcept {return modint(*this) *= rhs;}constexpr modint operator/(const modint rhs) const noexcept {return modint(*this) /= rhs;}constexpr modint &operator+=(const modint rhs) noexcept {a += rhs.a;if (a >= Modulus) {a -= Modulus;}return *this;}constexpr modint &operator-=(const modint rhs) noexcept {if (a < rhs.a) {a += Modulus;}a -= rhs.a;return *this;}constexpr modint &operator*=(const modint rhs) noexcept {a = a * rhs.a % Modulus;return *this;}constexpr modint &operator/=(modint rhs) noexcept {u64 exp = Modulus - 2;while (exp) {if (exp % 2) {*this *= rhs;}rhs *= rhs;exp /= 2;}return *this;}};#line 86 "main.cpp"constexpr ll MOD=1e9+7;constexpr ll MAX=1e9;using mint=modint<MOD>;struct Mul{using value_t=std::pair<ll,bool>;static constexpr value_t op(value_t a,value_t b){if(a.second||b.second)return {0,true};if(a.first*b.first>=MAX)return {0,true};return {a.first*b.first,false};}};struct Kaidan{using value_t=std::tuple<mint,mint,ll>;static constexpr value_t op(value_t a,value_t b){value_t ret;auto& [val,mul,size]=ret;mul=std::get<1>(a)*std::get<1>(b);size=std::get<2>(a)+std::get<2>(b);val=std::get<0>(a)*std::get<0>(b)*mypow(std::get<1>(a),std::get<2>(b));return ret;}};int main() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);ll n;std::cin>>n;std::vector<ll> a(n);for(auto&& e:a)std::cin>>e;if(std::any_of(all(a),[](ll m){return m==0;})){std::cout<<0<<"\n";return 0;}std::vector<std::pair<ll,bool>> tmp(n);rep(i,0,n){tmp[i].first=a[i];tmp[i].second=false;}std::vector<std::tuple<mint,mint,ll>> kai(n);rep(i,0,n){auto& [val,mul,size]=kai[i];val=mint(a[i]);mul=mint(a[i]);size=1;}mint ans=1;DisjointSparseTable<Mul> mul(tmp);DisjointSparseTable<Kaidan> kaidan(kai);rep(i,0,n){ll l=i+1,r=n+1;while(r-l>1){ll mid=(l+r)/2;if(mul.fold(i,mid).second)r=mid;else l=mid;}ans*=std::get<0>(kaidan.fold(i,l));}std::cout<<ans.value()<<"\n";return 0;}