BZOJ1009求解

表示BZOJ1009卡了我一天了。。。
没思路。。于是去搜题解。。
结果果然又是新技能
话说我为什么天天都会遇到新技能（显然我太弱了）
甚至题解也看不懂。。。
因为我对字符串处理和矩阵这俩玩意一无所知= =
果然还是太弱了。。然而并不想弃疗。。
DP已经懂了，然而。。然而。。。
然而我现在还是没搞懂是怎么把DP压缩成矩阵加速的（原谅我没写过矩乘(捂脸)）
如果是我根本没实力刷掉这题，那我该找什么知识点。。。求指教