この解説において，多項式ないし形式的冪級数 \(f(x)\) の \(i\) 次の係数を \([x^i]f(x)\) と書きます．

全ての操作結果に対して \(\displaystyle\prod_{i=1}^{N} B_i\) の総和を求めることを考えます．これを \(N^K\) で割れば期待値が得られます．

\(dp[i][j]\) を， \(N=i,\ A=(A_1,...,A_i),\ K=j\) とした時の\(\displaystyle\prod_{i=1}^{N} B_i\) の総和とします．最終的に求めるのは \(dp[N][K]\) です．

この時，遷移は次のようになります：
\(\displaystyle dp[i][j]=\sum_{k+l=j} dp[i-1][k]\cdot(A_i+l)\cdot\binom{j}{l}\)．
これを形式的冪級数で表現しやすいように書き換えます：
\(\displaystyle \frac{dp[i][j]}{j!} = \sum_{k+l=j} \frac{dp[i-1][k]}{k!}\cdot \frac{A_i+l}{l!}\)．
これを見ると， \(\displaystyle f_i(x)=\sum_{j=0}^{\infty} \frac{A_i+j}{j!}x^j\) とした時， \(\displaystyle[x^K]\prod_{i=1}^{N}f_i(x)\) が \(\displaystyle\frac{dp[N][K]}{K!}\) であることがわかります．

さて， \(\displaystyle [x^K]\prod_{i=1}^{N} f_i\) を高速に計算することを考えます．
\(\displaystyle f_i(x)=\sum_{j=0}^{\infty} \frac{A_i+j}{j!}x^j=A_i\sum_{j=0}^{\infty}\frac{1}{j!}x^j+\sum_{j=1}^{\infty}\frac{1}{(j-1)!}x^j=A_ie^x+xe^x=(A_i+x)e^x\)
となるので， \(\displaystyle \prod_{i=1}^N f_i(x) = e^{Nx} \prod_{i=1}^N (A_i+x)\) が得られます．
\(\displaystyle g(x):=\prod_{i=1}^N (A_i+x)\) は，愚直に行っても \(O(N^2)\) で計算できます．

結局，出力すべき \(\displaystyle \frac{dp[N][K]}{N^K}\) の値は
\(\displaystyle \sum_{i=0}^{\min(N,K)} N^{-K}\cdot K! \cdot [x^{K-i}]e^{Nx} \cdot [x^i]g(x) =\sum_{i=0}^{\min(N,K)} \frac{K!}{(K-i)!}\cdot N^{-i} \cdot [x^i]g(x)\)
となります．これは \(O(N)\) などで計算できるため，全体で \(O(N^2)\) でこの問題が解けました．