\(i-1\) 番目の数値が \(j\), \(i\) 番目の数値が \(k\) であるときの門松列の組み合わせの数を \(C(i, j, k)\), 合計を \(S(i, j, k)\) とすると, \(j \gt k\) の場合は

\[\begin{align} C(i+1, j, k) &= \sum_{l=0 \\ l \neq k}^{j-1} C(i, l, j) \\ &= \sum_{l=0}^{j-1} C(i, l, j) - C(i, k, j) \end{align}\] \[\begin{align} S(i+1, j, k) &= \sum_{l=0 \\ l \neq k}^{j-1} S(i, l, j) + kC(i+1, j, k) \\ &= \sum_{l=0}^{j-1} S(i, l, j) - S(i, k, j) + kC(i+1, j, k) \end{align}\]

となる. \(j \lt k\) の場合は \(l\) の範囲が変わるだけである.

\(\sum\) の部分は累積和を計算しておけば上記の計算は \(O(1)\) でできるので, 合計の計算量は \(O(NK^2)\) となる.