矩阵快速幂优化DP

矩阵满足：
（1）结合律：
ABC=A(Bc)
(2)分配率
AB+AC=A(B+C)
(3)特殊交换律
单位矩阵（对角线）。
前缀平方求和：
f[n]=n(n+1)*(2n+1)/6

一看到如此极端的数据范围肯定就是矩阵快速幂了。首先是AC自动机的DP板子，《文本生成器》，求长度固定的串中不出现给出串的串个数。dp[i][j]:表示i指针状态下，长度是j的文本串个数。

发现第一维度和第二三维度没有关系，我只需要统计每个被其他累加过多少次就行。我用bas[i][j]=k，代表。对n次系数快速幂计算，然后用乘上bas，第一行的tot+1个结果累加就是答案。

对于suma[i]和sumb[i]展开优化，发现suma[i]和sumb[i]可以直接从suma[i-1]和sumb[i-1]直接推出，所以在我们O(n)枚举断点的情况下
（前面可以取0，后面不可以），O(1)利用矩阵乘法就可以求出系数和答案。
假设断点是i，状态矩阵[sai,sbi]Bas-->[sa(i+1),sb(i+1)]，需要22矩阵系数转移，要注意顺序，就是
由Aibas1=A(i+1),A(i+1)bas2=A(i+2)....那么求矩阵的前缀就应该是fro[i]=fro[i-1]fro[i],我们已经求出的和在前面。
求后缀，就这样想，我已经有了bas(i+1)bas(i+2)bas(i+3)...bas(n)的答案矩阵，我要把bas(i)塞进去，它的实际递推式子应该是
bas(i)bas(i+1)bas(i+2)bas(i+3)...bas(n)=ans(i),所以后缀就是bac[i]=bac[i]bac[i+1]。
当然，如果你是BasA[i]=A[i+1]，那么就倒着想，ansi=bas(i)bas(i-1)bas(i-2)...*bas(1),也可以。