2012-0010

从 Trac 迁移的文章

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

原文章内容如下：

再占一个。。等到晚上再写，如果有童鞋现在想写的话可以抢走 by大肥羊


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

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


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


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

再占一个。。等到晚上再写，如果有童鞋现在想写的话可以抢走 by大肥羊

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

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

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

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