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 $$ be the geometric-series part of this expression modulo .

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 . First multiply the answer by . Then multiply every by . This order excludes the pair .

Precompute the inverses of $10^d-1$. To compute every $G_d(A_i)$, calculate once and then obtain by successive multiplication. Each case takes time and space.

Proof

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

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