※この解法は、高速な言語でないとACできない可能性があります。

多倍長整数を用いて、直接求めることができます。

import java.util.*
import java.math.BigInteger // 多倍長整数を使う
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val que = ArrayDeque<BigInteger>() // queの中身を全部掛ける
    repeat(N) {que.add(sc.nextBigInteger())} // まずは掛けたい要素を全部入れる
    while(que.size > 1) que.add(que.poll().multiply(que.poll())) // 要素が1個になるまで、二つ取り出して掛け算を繰り返す
    if (que.peek() > BigInteger.TEN.pow(18)) que.addFirst(BigInteger("-1")) // 10^18を超えていたら-1を出力
    println(que.poll())
  }
}

しかし、多倍長整数を用いて解こうとした方の中には、この方法では通らなかったと思う方もいるかもしれません。
そこで、何故この方法でACが取れるのかを多倍長整数の具体的な実装を踏まえて説明していきましょう。

なぜ多倍長整数ではTLEするのか

まずは、TLEの原因について説明します。

一般に、掛け算というのは遅いものです。 筆算を想像してもらえば、桁数が多い掛け算は大変そうだというイメージが想像できるのではないでしょうか？

具体的には、 \(X\) 桁の数と \(Y\) 桁の数を掛け算するとき、愚直には \(\Theta(XY)\) 時間が掛かります。
従って、今回の問題の場合、前から順に掛け算を行うと \(i\) 回目の掛け算では最悪 \(\Theta(i \log A)\) 桁程度になっており、そこに \(\log A\) 桁の値を掛け算するので、計算量は最悪 \(\Theta( \sum_{i=1}^{N} i\log^2A) = \Theta(N^2\log^2A)\) 程度の計算時間が掛かります(※実際には、現代のPCは \(\log A\) 桁の掛け算をまとめて定数時間でできるので \(\Theta(N^2)\) 時間で終わります)。

高速な掛け算アルゴリズム

さて、掛け算は愚直に筆算すると \(\Theta(XY)\) 時間であることを述べました。

しかし、実はもっと速い掛け算も存在します。

一つ目はKaratsuba法と呼ばれる方法で、計算量は \(M=\max(X, Y)\) として \(O(M^{\log_2 3}) = O(M^{1.59})\) です。
定数倍も、愚直には劣りますが比較的良好な速度のため、多くの言語では桁数が増えてくるとこのアルゴリズムを用います。

二つ目はToom-Cook法と呼ばれる方法で、ある正整数 \(k\) を定めたときに \(O(M^{\log_k (2k-1)})\) 時間で求めることができます。
ただし、 \(k\) が大きいほど急激に遅くなるため、実用上は \(k=3\) とした \(O(M^{\log_3 5}) = O(M^{1.47})\) 時間アルゴリズムが使われることが多いです。

三つ目はAtCoder Libraryでもおなじみ高速フーリエ変換を用いた方法で、Schönhage–Strassen法と呼ばれています。
計算量は \(O(M \log M)\) なのですが、定数倍がかなり悪いために \(M \geq 10^4\) のような巨大な数でのみ高速に動作します。

高速な掛け算を上手く利用する

さて、上で紹介した高速な掛け算アルゴリズムは多くの言語でも標準で実装されているため、素直に多倍長整数を用いても \(o(N^2)\) になる気がします。
しかし、実際には最悪 \(\Theta(N^2)\) となるテストケースが存在します。これは何故なのでしょうか？

実は、高速な掛け算アルゴリズムは、いずれも桁数が多い方の値に計算量が依存しています。
これにより、前から愚直に計算すると大きな桁の数×小さな桁の数という計算を繰り返すことになり、高速な掛け算の恩恵を受けることができません。

そこで、小さな数は小さな数同士と、大きな数は大きな数同士と掛け算を行うように計算順序を適切に変更することで、高速化を行うことができます。

このような順序は幾つかありますが、例えばトーナメントのように計算を行っていくのは一つの手です。
例えば \(A_1\) から \(A_8\) までを掛けたいとき、以下のように計算を行います。

\((((A_1 \times A_2) \times (A_3 \times A_4)) \times ((A_5 \times A_6) \times (A_7 \times A_8)))\)

これによって高速な掛け算アルゴリズムの恩恵を受けることができ、 \(O(N \log^2N)\) などで解くことができます。

ですが、綺麗なトーナメントにならないときはどう実装すればいいのでしょうか？
優先度付きキューで小さい値から順に2個取り出して掛け算をするという手もありますが、比較を行う分だけ定数倍が悪くなります。
実はキューを用いて掛け算を行っても計算量が悪化しないことが示せて、これによって簡潔に実装を行うことができます。

最後に

今回紹介した方法はあくまで多倍長整数でも通るということを示しただけであり、計算量が悪いアルゴリズムであるということは変わりありません。

普段はなかなか意識しづらい計算量という存在ですが、これを機に標準ライブラリの計算量についても少し意識するようになれば幸いです。