tkdsheep-solution-0010

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
此题的做法是矩阵乘法，比较难的地方是矩阵的表示以及转移，反正我比赛的时候很土，一直想不清楚怎么转移

首先每一列有K个格子，那么我们用一个1xK的矩阵来表示ans=[a0 ,a1 ... ,aK-1], ai表示最后从这一列的第i个格子走出来有多少种方案
则最开始第0列的时候任意格子都可以站，所以初始ans=[1,1,1,...,1]

接下来每遇到新的一列，可以用一个NxN的矩阵c来表示这一列的转移方案，ci,j表示这一列从格子i进去，从格子j出去，是否有这样一条通路
找通路很简单，如果格子是0，则这个格子不能进，不能出，如果格子是1，则从这里进就从这里出，即ci,i=1，如果格子是2，则从这个格子进，要从另外一个格子2出，且它们之间由多个格子1相连

最后用ans和c作矩阵乘法，更新ans即完成一列的转移，如果这一列是重复很多次，则可以用矩阵快速求幂 

}}}

此题的做法是矩阵乘法，比较难的地方是矩阵的表示以及转移，反正我比赛的时候很土，一直想不清楚怎么转移
首先每一列有K个格子，那么我们用一个1xK的矩阵来表示ans=[a0 ,a1 ... ,aK-1], ai表示最后从这一列的第i个格子走出来有多少种方案
则最开始第0列的时候任意格子都可以站，所以初始ans=[1,1,1,...,1]
接下来每遇到新的一列，可以用一个NxN的矩阵c来表示这一列的转移方案，ci,j表示这一列从格子i进去，从格子j出去，是否有这样一条通路
找通路很简单，如果格子是0，则这个格子不能进，不能出，如果格子是1，则从这里进就从这里出，即ci,i=1，如果格子是2，则从这个格子进，要从另外一个格子2出，且它们之间由多个格子1相连
最后用ans和c作矩阵乘法，更新ans即完成一列的转移，如果这一列是重复很多次，则可以用矩阵快速求幂