N rooms

Let $P=p_0+p_1+\cdots+p_N$. Let $E_i$ be the expected total time spent in room $i$ before the process ends, and define $E_{N+1}=0$.

For door $i$, let $R_i$ be the number of crossings from left to right and $L_i$ the number of crossings from right to left. Ddas starts to the left of door $i$ and finishes to its right, so every execution satisfies

$$R_i-L_i=1.$$

During each minute spent in room $i$, Ddas crosses door $i$ to the right with probability $\frac{p_i}{P}$. Hence

$$\mathbb E[R_i]=E_i\frac{p_i}{P}.$$

Similarly,

$$\mathbb E[L_i]=E_{i+1}\frac{p_i}{P}.$$

Subtracting gives

$$(E_i-E_{i+1})\frac{p_i}{P}=1,$$

and therefore

$$E_i-E_{i+1}=\frac{P}{p_i}.$$

Summing this identity from $i$ through $N$ and using $E_{N+1}=0$ gives

$$E_i=P\sum_{k=i}^{N}\frac{1}{p_k}.$$

Thus, after computing the modular inverses of all $p_i$, all answers can be obtained by maintaining a suffix sum of the inverses.

Computing every inverse separately with Fermat's little theorem takes $O(N\log 998244353)$ time. The reference solution instead uses batch inversion: it builds prefix products, computes the inverse of the total product once, and proceeds backward. This takes $O(N+\log 998244353)$ time.

Solution written by GPT5.6