beet's soil

競プロのことなど

n次元空間を(n-1)次元平面で切るDP

n 変数のdpを多項式  f(x_1, x_2, \ldots, x_n) と置く
遷移を  g(x_1, x_2, \ldots, x_n) = \sum_i \prod_j {x_j}^{e_{ij}} とする  (e_{ij} \ge 0)

このとき定数  a_1, a_2, \ldots, a_n, K \ge 0 と変数  p_1, p_2, \ldots, p_n \ge 0 に対して  \displaystyle \sum_{\sum_{i} a_i p_i = K} \left [\prod_{j} {x_j}^{p_j} \right ] f(x_1,x_2, \ldots, x_n) を求めたいとする。

 x_i = x^{a_i} とおくと、  f, g は共に一変数多項式と見なすことができるので、一次元のDPに帰着できる。

本質は平面全体の総和をまとめて数えられることと、平面上のどこにあるかが遷移に関係ないこと。

利用例

 n = 2, a_1 = a_2 = 1, K = 0, 1, \ldots, n-1
 f_0 = 1, g_k(x_1, x_2) = \displaystyle \sum_{i} \left (x_1 {x_2}^k \right)^i