2010-1155

从 Trac 迁移的文章

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

原文章内容如下：

先简述一下题意：
      有n*m的格子矩阵，n,m不超过8，刚开始是没有石子的，每个格子有一串操作，操作的长度不超过6，全部格子同时进行操作，每秒一个进行操作，每个格子做完最后一个操作，下一个操作为第一个，一直循环下去，直到时间t秒。操作可能是放一些石头进该格子；把该格子的石子移到紧贴的四个格子之一；把该格子清空。求时间t时全部格子里石子数最多的格子的石子数。

比较正统的解法：
      因为操作长度不超过6，所以经过一定时间后，所有操作都会同时回到第一个，这个时间的最小值就是他们的最小公倍数，设为P。
      这样我们可以先做P秒，用模拟就好了，因为P很小；然后每次都做P秒，这个可以用logN的矩阵乘法。

很快捷的解法：
      这些格子进行的这些操作，可以发现每个格子的石子数经过一个周期增加的是一个常量，这样可以先模拟两个周期，算出每个格子的增量，然后等差数列求和。

先简述一下题意：

有n*m的格子矩阵，n,m不超过8，刚开始是没有石子的，每个格子有一串操作，操作的长度不超过6，全部格子同时进行操作，每秒一个进行操作，每个格子做完最后一个操作，下一个操作为第一个，一直循环下去，直到时间t秒。操作可能是放一些石头进该格子；把该格子的石子移到紧贴的四个格子之一；把该格子清空。求时间t时全部格子里石子数最多的格子的石子数。

比较正统的解法：

因为操作长度不超过6，所以经过一定时间后，所有操作都会同时回到第一个，这个时间的最小值就是他们的最小公倍数，设为P。

这样我们可以先做P秒，用模拟就好了，因为P很小；然后每次都做P秒，这个可以用logN的矩阵乘法。

很快捷的解法：

这些格子进行的这些操作，可以发现每个格子的石子数经过一个周期增加的是一个常量，这样可以先模拟两个周期，算出每个格子的增量，然后等差数列求和。