比较人性的一个题目。

考虑对于朴素的 DP，我们设 $f_i$ 表示以第 $i$ 个裂缝截止可以获得的答案，那么如果这个裂缝没有标记，转移方程就是：

$f_i=\sum\limits_{j=0}^{i-1}f_{j}\times(i-j)^2$

否则就有 $f_i=0$。

显然对于一个 $n$ 有 $10^9$ 的状态我们应该用矩阵乘法优化，那么直接的思路就是把特殊点分割的每一段都用矩阵乘法优化，所以现在只考虑 $i+1$ 不是特殊点的转移方法。

考虑对转移进行简单变形，得到：

$f_{i+1}=\sum\limits_{j=0}^{i} f_j\times(i+1-j)^2$

把 $f_i$ 拿出来得到：

$f_{i+1}=f_i+\sum\limits_{j=0}^{i-1} f_{j}\times (i-j+1)$

打开后面的括号得到：

$f_{i+1}=f_i+\sum\limits_{j=0}^{i-1}f_{j}\times (i-j)^2+2\sum\limits_{j=0}^{i-1}f_j\times (i-j)+\sum\limits_{j=0}^{i-1}f_j$

那么设：

$a_i=\sum\limits_{j=0}^{i-1}f_j,\ b_i=\sum\limits_{j=0}^{i-1}f_j\times(i-j),\ c_i=\sum\limits_{j=0}^{i-1}f_j\times(i-j)^2$

那么容易发现其实 $f_i=c_i$，所以分情况讨论得到：

如果 $i+1$ 不是特殊的：

• $a_{i+1}=a_i+c_i$
• $b_{i+1}=a_i+b_i+c_i$
• $c_{i+1}=a_i+2b_i+2c_i$

如果 $i+1$ 是特殊的：

• $a_{i+1}=a_i$
• $b_{i+1}=a_i+b_i$
• $c_{i+1}=a_i+2b_i+c_i$

那么通过这个转移构建的矩阵如下，分别是不特殊和特殊：

$\begin{bmatrix} a_{i+1} \\ b_{i+1} \\ c_{i+1} \end{bmatrix}=\begin{bmatrix} a_{i} \\ b_{i} \\ c_{i} \end{bmatrix}\times \begin{bmatrix} 1 &0 & 1\\ 1 & 1 & 1\\ 1 & 2 &2 \end{bmatrix}$

$\begin{bmatrix} a_{i+1} \\ b_{i+1} \\ c_{i+1} \end{bmatrix}=\begin{bmatrix} a_{i} \\ b_{i} \\ c_{i} \end{bmatrix}\times \begin{bmatrix} 1 &0 & 0\\ 1 & 1 & 0\\ 1 & 2 &1 \end{bmatrix}$

时间复杂度为 $O(m\log n)$。