Let us denote \(p=\frac{P}{100}\) and \(q=1-p\). Without loss of generality, we can assume that we start with \(Q=((2,1),(N,1))\).

The sequence \(D\) is updated \(N-1\) times. For the \(i\)-th update, let \((x,y)\) be the foremost element of the queue \(Q\). If this element was added to \(Q\) during the processing of vertex \(x-1\), we label it as L, and if it was added during the processing of vertex \(x+1\), we label it as R.

Then, we can see that the possible sequences of operations correspond one-to-one with the sequences \(S\) of length \(N-1\) consisting of L and R such that \(S_1 =\)L.

The probability of obtaining a sequence \(S\) through operations is calculated by, for \(i=1,\ldots,N-2\), multiplying \(p\) if \(S_i=S_{i+1}\) and \(q\) if \(S_i\neq S_{i+1}\).

Furthermore, if we let \(l\) be the number of Ls and \(r\) be the number of Rs in \(S\), the sum of the elements of \(D\) can be expressed as \(\frac{l(l+1)}{2} + \frac{r(r+1)}{2}\).

Now, we consider calculating the sum, over all possible \(S\), of \(\frac{l(l+1)}{2}\) multiplied by the probability of obtaining that \(S\). (The same can be done for the \(\frac{r(r+1)}{2}\) part.)

\(\frac{l(l+1)}{2}\) is equal to the number of ways to choose two occurrences of L from \(S\) with repetition allowed, so we can determine \(S\) from the beginning and the answer can be calculated using dynamic programming that keeps track of the six possible states representing the last element and the number of Ls chosen so far.

Moreover, this dynamic programming can easily be reformulated as matrix exponentiation. Since the number of states is constant, this problem can be solved in \(\mathrm{O}(\log N)\) time per test case.