CF2204G Grid Path 题解

容易想到设 $f_{k,i,j}$ 表示当前处理了前 $k$ 行的染色情况，第 $k$ 行恰好染色了 $[i,j]$ 区间内的所有格子，方案数是多少。然后注意到这个东西的转移可以用矩阵乘法优化，做到 $O(m^6\log n)$ 时间复杂度求解。

考虑继续优化。注意到关键性质：对于具有可减性的信息，$[l,r]$ 区间的信息可以被表示为 $[0,r]+[l,m-1]-[0,m-1]$。此时所有区间都形如 $[0,m-1]$ 整体的前后缀，可以用 $2m$ 个区间来表示所有区间。转移直接枚举前后缀区间然后再枚举要转移的区间 $[l,r]$ 将 $[l,r]$ 拆分成三个前后缀区间后分别按系数转移即可，同样可以用矩阵乘法优化。此时算法的时间复杂度被优化到 $O(m^3\log n)$，简单卡常后可以通过该题。