簡単のため \(k=N\) について解くと思って説明します．計算量の解説は省略しますが，公式解説と同じ計算量オーダーになります．

長さ \(L\) の区間 \(1,2,\ldots,N\) を用意して，これら全体が \([0,NL]\) を表すとして考えます．操作は次のように言い換えられます．

• 各区間 \(i\) に対して赤いボールをひとつずつ置く．置く場所は指定された \(M\) 箇所から一様ランダム．
• 青いボールはまずどの区間に置くかを選び，そのあとで置く場所を選ぶ．

青いボールを置く区間番号の列を決めるごとに答を求めると考えると，おおよそ次のようになります．

\(1\) 以上 \(N\) 以下の整数からなる列 \((x[1],x[2],\ldots,x[N])\) を以下の条件下で重み付きで数えてください．

条件：任意の \(n\) について，\(x[i]\leq n\) となる \(i\) の個数は \(n\) 以下．

重み：\(x[i]\leq n\) となる \(i\) の個数がちょうど \(n\) 個であるような \(n\) それぞれについて，\(x[i]=n\) となる \(i\) の個数が \(k\) であるとき，重み \(w_k\) がかかる．

重み \(w_k\) は，入力の \(A\) から計算できます．おおよそ \(\sum_i A_i^k\) を計算することに対応します．

重みのかかる \(n\) のところで切って考えると，次のような方針で解けることが分かります．まず次の答を \(f_n\) とします．

\(1\) 以上 \(n\) 以下の整数からなる列 \((x[1],x[2],\ldots,x[n])\) を以下の条件下で重み付きで数えてください．

条件：\(m\neq n\) について，\(x[i]\leq m\) となる \(i\) の個数は \(m\) 未満．

重み：\(x[i]=n\) となる \(i\) の個数が \(k\) であるとき，重み \(w_k\) がかかる．

そして，\(f(x)=\sum_{n\geq 1}f_n\frac{x^n}{n!}\) について \([x^N]\frac{1}{1-f(x)}\) が求めるもの（に \(N\) の簡単な関数をかけたもの）になります．

\(f_n\) は，かかる重みで分類して \(f_n = \sum_{k}c_{n,k}w_k\) のように書けます．\(c_{n,k}\) は，次のような数え上げです．

\(1,2,...,n\) からなる長さ \(n-k\) の列であって、任意の \(m\) に対して，\(m\) 未満であるものの個数が \(m\) 未満になっているものの個数．

これは parking function と同種の有名数え上げで，\((k-1)(n-1)^{n-k-1}\) のようなかなり簡単な解になります（コンテスト中は愚直を書いて実験するのもよいと思います）．

これを用いて変形すると，結局最終的に次の問題に帰着されます．

\(a_1,\ldots,a_N\) が与えられる．\(b_n = \sum_k a_k\frac{n^{n-k}}{(n-k)!}\) により定まる \(b_1,\ldots,b_N\) を求めよ．

言い換えると \(b_n = [x^n] A(x)e^{nx}\) ということになっていて，ラグランジュ反転を利用すると，\(xe^{-x}\) の合成逆と何かの関数合成という形で計算できます．