tkdsheep-solution-0017
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
n个点构成的环上，每个点有两种属性（分别用整数P和Q来表示），P和Q的范围会很大，并且要保证相邻两个点至少有一个属性值是一样的，现在给定其中8个点的属性值，要求剩下的点有多少种方案
这题n、P、Q的范围都很大，很容易就可以猜到是求递推关系然后用矩阵乘法
因为这是一个环，所以随便哪个点作为起点都是一样的，为了方便，这里就选x坐标最小的点作为起点，然后我们就要去找递推关系，起点当然只有1种方案，然后我们来看下面这个例子
1...2......3..4...
1表示给定属性的第一个点，2表示给定属性的第2个点（都是按X坐标拍过序的）
'.'表示其余的未给定的点
由于题目要求相邻两个点至少要有一种属性相同，那么假设第2个点的两个属性值分别是A,B，从第1个给定点转移到第2个给定点的过程中，每个中间点的属性值只有4种情况：[xy,xB,Ay,AB]
这里x表示第一个属性不为A的任意值，y表示第二个属性不为B的任意值
所以可以根据点1和点2的具体属性值来确立初始矩阵，比如点1的属性值为（3,7），点2的属性值为（3,8），那么它们只有属性1相同（即Ay=1），则初始矩阵为[0,0,1,0]，其它3种情况类似
这样就确定了初始矩阵T=[xy,xB,Ay,AB]的值
然后每次怎么转移？
这个最好自己推一下，不难的，这里我直接贴出来吧，转移矩阵D是
[p+q-3, 1 , 1 ,0,
q-1 ,p-1, 0 ,1,
p-1 , 0 ,q-1,1,
0 ,p-1,q-1,1],
为什么？随便举个例子吧，比如p+q-3是怎么来的，它表示上一个点的属性是xy的情况下，下一个点的属性还是xy有多少种方案，那么根据容斥，当然就是（p-1）+（q-1）-1
所以每次乘一下这个矩阵D，就能转移一个点，点1到点2的距离是3个点，所以要乘3次，每次都乘D，用快速求幂就OK
注意每转移完一段，都要重置初始矩阵T，重置方法跟前面类似，也是根据两个相邻给定点的属性关系来确定的
最后乘回到起点，矩阵中代表AB的元素就是答案
bonus：这道题也是一个类似的分段矩阵乘法，有兴趣可以看看
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3538n个点构成的环上，每个点有两种属性（分别用整数P和Q来表示），P和Q的范围会很大，并且要保证相邻两个点至少有一个属性值是一样的，现在给定其中8个点的属性值，要求剩下的点有多少种方案
这题n、P、Q的范围都很大，很容易就可以猜到是求递推关系然后用矩阵乘法
因为这是一个环，所以随便哪个点作为起点都是一样的，为了方便，这里就选x坐标最小的点作为起点，然后我们就要去找递推关系，起点当然只有1种方案，然后我们来看下面这个例子
1...2......3..4...
1表示给定属性的第一个点，2表示给定属性的第2个点（都是按X坐标拍过序的）
'.'表示其余的未给定的点
由于题目要求相邻两个点至少要有一种属性相同，那么假设第2个点的两个属性值分别是A,B，从第1个给定点转移到第2个给定点的过程中，每个中间点的属性值只有4种情况：[xy,xB,Ay,AB]
这里x表示第一个属性不为A的任意值，y表示第二个属性不为B的任意值
所以可以根据点1和点2的具体属性值来确立初始矩阵，比如点1的属性值为（3,7），点2的属性值为（3,8），那么它们只有属性1相同（即Ay=1），则初始矩阵为[0,0,1,0]，其它3种情况类似
这样就确定了初始矩阵T=[xy,xB,Ay,AB]的值
然后每次怎么转移？
这个最好自己推一下，不难的，这里我直接贴出来吧，转移矩阵D是
[p+q-3, 1 , 1 ,0,
q-1 ,p-1, 0 ,1,
p-1 , 0 ,q-1,1,
0 ,p-1,q-1,1],
为什么？随便举个例子吧，比如p+q-3是怎么来的，它表示上一个点的属性是xy的情况下，下一个点的属性还是xy有多少种方案，那么根据容斥，当然就是（p-1）+（q-1）-1
所以每次乘一下这个矩阵D，就能转移一个点，点1到点2的距离是3个点，所以要乘3次，每次都乘D，用快速求幂就OK
注意每转移完一段，都要重置初始矩阵T，重置方法跟前面类似，也是根据两个相邻给定点的属性关系来确定的
最后乘回到起点，矩阵中代表AB的元素就是答案
bonus：这道题也是一个类似的分段矩阵乘法，有兴趣可以看看
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3538