Pi Problem

Let $P=998\,244\,353$. If $a$ has $d$ decimal digits, then

$$\mathrm{rep}(a,b)=a\sum_{k=0}^{b-1}10^{dk}=a\frac{10^{db}-1}{10^d-1}.$$

For $1\leq d\leq10$, $10^d-1$ is not divisible by $P$, so we can divide using its modular inverse. Let $G_d(b)$ be the geometric-series part of this expression modulo $P$.

Let $d_i$ be the number of digits in $A_i$. The product over all pairs with left endpoint $i$ is

$$A_i^{N-i}\prod_{j=i+1}^{N}G_{d_i}(A_j).$$

Scan from right to left and maintain a suffix product $S_d=\prod_{j>i}G_d(A_j)$ for each digit count $d$. First multiply the answer by $A_i^{N-i}S_{d_i}$. Then multiply every $S_d$ by $G_d(A_i)$. This order excludes the pair $(i,i)$.

Precompute the inverses of $10^d-1$. To compute every $G_d(A_i)$, calculate $x=10^{A_i}\bmod P$ once and then obtain $x^1,x^2,\cdots,x^{10}$ by successive multiplication. Each case takes $O(N(10+\log N+\log\max A_i))$ time and $O(N)$ space.

Proof

Immediately before processing $i$, $S_d$ is exactly the product of $G_d(A_j)$ over all $j>i$. Initially there are no elements to the right, so every $S_d=1$. After multiplying the contribution of $i$ into the answer, multiplying $S_d$ by $G_d(A_i)$ preserves the invariant for the next index.

Each pair $(i,j)$ contributes one factor of $A_i$ and one factor of $G_{d_i}(A_j)$ when its left endpoint $i$ is processed. It is not included at any other step. Thus, the final answer is the required product over all pairs.

In subtask 1, the repeated number can be built directly. In subtask 2, evaluate the geometric-series formula for every pair. In subtask 3, every value has one digit, so only one suffix product is needed. For the full constraints, maintain one suffix product for each of the ten possible digit counts.

Solution written by GPT5