結果
| 問題 | 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(...)
#endif
void 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;
}