team2012-D1-sol-0017

从 Trac 迁移的文章

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

原文章内容如下：

=== 题目大意 ===
有一个 N 个顶点的多边形, 每个顶点有两个属性 A 和 B, 其中 A 可以被 P 种颜色染色, B 可以被 Q 种颜色染色. 其中合法的染色方案是相邻两个顶点至少有一种属性的颜色相同. 现在给出其中 8 个顶点的 A, B 属性. 求问一共有多少种染色方案.

=== 数据范围 ===
 * 1 <= N, P, Q <= 10^10

=== 解题思路 ===
一看 N 的范围这么大, 就知道肯定是低于线性时间复杂度的解法, 一般就是快速幂了 (时间复杂度为 O(log(N))). 很快就可以想到是用矩阵乘法来做转移. 一开始我想的是 (a,b) 到 (c,d), 中间的顶点的染色方案只要 care A 属性是 a/c/其他, B 属性是 b/d/其他, 这样组合以后就有 9 种染色方案, 那么矩阵就是 9*9 的.... 后来发现从 (a,b) 转移到 (c,d), 你不需要去 care a, b, 你只要关心 A 属性是否为 c, B 属性是否为 d 就好了. (a,b)作为起始状态, 只要判断一下是 (c,d), (c,!=d), (!=c, d) 和 (!=c, !=d) 这四种情况中的哪一种就好了. 于是转移矩阵就变成了 4*4 的. 手推一下可以求出这个矩阵 (具体看代码).

这题作为矩阵乘法算方案数的题目应该是很不错的, 思路也很典型.

题目大意

有一个 N 个顶点的多边形, 每个顶点有两个属性 A 和 B, 其中 A 可以被 P 种颜色染色, B 可以被 Q 种颜色染色. 其中合法的染色方案是相邻两个顶点至少有一种属性的颜色相同. 现在给出其中 8 个顶点的 A, B 属性. 求问一共有多少种染色方案.

数据范围

• 1 <= N, P, Q <= 10^10

解题思路

一看 N 的范围这么大, 就知道肯定是低于线性时间复杂度的解法, 一般就是快速幂了 (时间复杂度为 O(log(N))). 很快就可以想到是用矩阵乘法来做转移. 一开始我想的是 (a,b) 到 (c,d), 中间的顶点的染色方案只要 care A 属性是 a/c/其他, B 属性是 b/d/其他, 这样组合以后就有 9 种染色方案, 那么矩阵就是 9*9 的.... 后来发现从 (a,b) 转移到 (c,d), 你不需要去 care a, b, 你只要关心 A 属性是否为 c, B 属性是否为 d 就好了. (a,b)作为起始状态, 只要判断一下是 (c,d), (c,!=d), (!=c, d) 和 (!=c, !=d) 这四种情况中的哪一种就好了. 于是转移矩阵就变成了 4*4 的. 手推一下可以求出这个矩阵 (具体看代码).

这题作为矩阵乘法算方案数的题目应该是很不错的, 思路也很典型.