zrj2012-B3-0017

从 Trac 迁移的文章

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

原文章内容如下：

题目大意：有N个点构成一个环，每个点有两种属性，第一个属性在1~P之间，第二个在1~Q之间，且相邻两个点必须有至少一个属性值是一样地。现在有8个点是已经固定好属性的，求其余点的总状态数。
这题是用矩阵快速幂来做。8个点把环分成8段，我们一次顺时针处理。对于每一段，拉成直线，每个点可能有4种状态：1、只有属性1与右端点相同；2、只有属性2与右端点相同；3、两个属性都与右端点相同；4、两个属性都不与右端点属性相同。然后，我们可以形成一个4*4的转移矩阵，进行矩阵快速幂，左端点的状态即使初始状态，是确定的。
PS：MS8个点中会有相同坐标的点出现，需要特判。

题目大意：有N个点构成一个环，每个点有两种属性，第一个属性在1~P之间，第二个在1~Q之间，且相邻两个点必须有至少一个属性值是一样地。现在有8个点是已经固定好属性的，求其余点的总状态数。

这题是用矩阵快速幂来做。8个点把环分成8段，我们一次顺时针处理。对于每一段，拉成直线，每个点可能有4种状态：1、只有属性1与右端点相同；2、只有属性2与右端点相同；3、两个属性都与右端点相同；4、两个属性都不与右端点属性相同。然后，我们可以形成一个4*4的转移矩阵，进行矩阵快速幂，左端点的状态即使初始状态，是确定的。

PS：MS8个点中会有相同坐标的点出现，需要特判。