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

う

n 変数のdpを多項式 f(x1,x2,…,xn)$f(x_1,x_2,\dots ,x_n)$ と置く
遷移を g(x1,x2,…,xn)=∑i∏jxjeij$g(x_1,x_2,\dots ,x_n)=\sum _i\prod _j{x_j}^{e_{ij}}$ とする (eij≥0)$(e_{ij}\ge 0)$

このとき定数 a1,a2,…,an,K≥0$a_1,a_2,\dots ,a_n,K\ge 0$ と変数 p1,p2,…,pn≥0$p_1,p_2,\dots ,p_n\ge 0$ に対して ∑∑iaipi=K[∏jxjpj]f(x1,x2,…,xn)${\displaystyle \sum _{\sum _i{a}_i{p}_i=K}\left[\prod _j{x_j}^{p_j}\right]f(x_1,x_2,\dots ,x_n)}$ を求めたいとする。

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

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

利用例

n=2,a1=a2=1,K=0,1,…,n−1$n=2,a_1=a_2=1,K=0,1,\dots ,n-1$
f0=1,gk(x1,x2)=∑i(x1x2k)i$f_0=1,g_k(x_1,x_2)={\displaystyle \sum _i{\left(x_1{x_2}^k\right)}^i}$