管理する多項式をシフトすることでも時間計算量 \(O(N^6)\) を達成することができます。

多項式 \(\mathrm{dp}(i,j, k)\) を potato167 さんの解説 と同じく定義しします。このとき \(y = 1 + x\) とおくと、同解説で述べられている遷移は次のように書き換えられます。

\[ \mathrm{dp}(i + a, a, i - k + a) \ \overset{+}{\longleftarrow} \ \mathrm{dp}(i, j, k) \cdot \binom{N - i}{a} \cdot y ^ {a(a-1)/2} \cdot (y^j - 1)^a \]

これは \(a\) に関するイテレーションを通して \(\mathrm{dp}(i, j, k) \cdot y ^ {a(a-1)/2} \cdot (y^j - 1)^a\) を管理することで高速化できます。なぜならこの多項式の更新は疎な多項式 \(y^a (y^j - 1)\) を掛けるだけでよいので次数に関して線形で行うことができるためです。

計算量は次のようになっています。

• 二項係数の前計算 \(O(N^4)\)
• DP \(O(N^6)\)（状態 \(O(N^3)\) 個、遷移先 \(O(N)\) 個、遷移時間 \(O(N^2)\)）
• シフトされた多項式の復元 \(O(N^4)\)

Rust 30 ms