以下 \(p=\frac{P}{100},q=1-p\) とします．\(Q=((2,1),(N,1))\) の状態から始めるとして一般性を失いません．

\(D\) の更新は \(N-1\) 回行われますが，その内 \(i\) 回目の更新時の \(Q\) の先頭 \((x,y)\) が，頂点 \(x-1\) の処理の際に \(Q\) に入れられた場合 L，頂点 \(x+1\) の処理の際に \(Q\) に入れられた場合 R と呼ぶことにします．

このとき，長さ \(N-1\) の LR 列 \(S\) であって \(S_1 =\)L を満たすものが操作と一対一に対応していることが分かります．

操作によって \(S\) が得られる確率は，\(i=1,\ldots,N-2\) に対して，\(S_i=S_{i+1}\) ならば \(p\) を，\(S_i\neq S_{i+1}\) ならば \(q\) を掛けることによって求まります．

更に，\(S\) に出現する L の個数を \(l\), \(S\) に出現する R の個数を \(r\) とすると，\(D\) の要素の総和は \(\frac{l(l+1)}{2} + \frac{r(r+1)}{2}\) と表せます．

以下では考えられる \(S\) 全てに対して \(\frac{l(l+1)}{2}\) に \(S\) が得られる確率を掛けたものの総和を求めることを考えます．（\(\frac{r(r+1)}{2}\) 部分も同様に行えます．）

\(\frac{l(l+1)}{2} \) は \(S\) の中の L を重複を許して \(2\) 個選ぶ方法に等しいので，\(S\) を先頭から決めていき，末尾及び今 L を何個選んだかの \(6\) 通りを状態として持つ動的計画法により答えが計算できます．

更に，この動的計画法は簡単に行列累乗の形で書き直すことができます．状態が定数個なので，この問題はテストケースあたり \(\mathrm{O}(\log N)\) で解くことができます．