矩阵优化DP

bzoj 4417

按照其给定的棋盘走法,每次走奇数步。那么有\(f_{i,j}=f_{i-1,j\pm 1}+f_{i-3,j\pm 1}+f_{i-5,j\pm 1}…\),
即\(f_{i,j}=f_{i-1,j\pm 1}+f_{i-2,j}\)。

定义矩阵列:\(j \in [0,n-1]\)列表示\(f_{i-1,j}\),\(j \in [n,2n-1]\)列表示\(f_{i-2,j}\)。
\(j \in [0,n-1]\)行表示\(f_{i,j}\),\(j \in [n,2n-1]\)行表示\(f_{i-1,j}\)。
从\(f_{i-2} \rightarrow f_{i}\)转移斜对角线为1。从\(f_{i-1} \rightarrow f_{i-1}\)斜对角线为1。
从\(f_{i-1} \rightarrow f_{i}\)有\(base[i][i-1~i+1]\)为1。
那么矩阵就可以实现转移了。

bzoj 4870
题意:求\(\sum \textrm{C}_{nk}^{ik+r}\)。
设矩阵表示模k余r的和。\(f[i][j]=f[i-1][j]+f[i-1][(j-1+k)\% k]\)。
改改矩阵乘法就好了。

Leave a Reply

Your email address will not be published. Required fields are marked *