题解：P7794 [COCI 2014/2015 #7] JANJE
S_Y_B_S
·
·
题解
P7794 [COCI 2014/2015 #7] JANJE 题解
思路
显然，每张图的上色方案数即为图的方案数与颜色的方案数之积。
先考虑每张图的方案数。
容易发现，每张图都不可能在满足要求的情况下只使用一种颜色涂完。
特殊地，图 1、3、4、8 不仅可以使用三种颜色完成，还可以使用两种颜色完成。
图 1：3\times 2^{19} 或 2 种。
图 2：3 \times 2^5 种。
图 3：3\times 2^3 或 2 种。
图 4：3\times 2^{13} 或 2 种。
图 5：3 \times 2^1 种。
图 6：3 \times 2^5 种。
图 7：3 \times 2^5 种。
图 8：这幅图如果用三种颜色去涂，答案很玄学，并非简单的 3\times 2^{28} 种，因为要考虑这个环的首尾两个区域的关系，正确的答案是 1073741826 种。这幅图只用 2 种颜色涂色，结果是 2 种。
每幅图的答案即为使用三种颜色的方案数乘上 C_k^3，加上使用两种颜色的方案数（如果有的话）乘上 C_k^2（注意直接计算会有重复，在计算使用三种颜色的方案数时需要减去 A_3^2 再去乘 C_k^3）。
Tips
-
可以通过数组来便捷地计算每一幅图的方案数。
-
计算时记得用long long。
这道题码量很小，关键在思路，不贴代码。