集训队作业puncher解题报告

湖南长郡中学王俊《Puncher》解题报告问题简述有一个n行m列的矩阵，将其中的某些格子染色（至少一个），如果两种染色方案通过如下变换以后相同，则认为是本质相同的。当时，进行90、180、270度的旋转；当时，进行180度的旋转。当时，进行左右翻转，上下翻转和沿着某条对角线翻转；当时，进行左右翻转，上下翻转。向上、下、左、右四个方向平行移动。但如果移动造成某个被染色的格子被移出矩阵，则不允许。举例说明：，两个格子被染色，则有如下两种不同的方案：求所有本质不同的染色方案。分析这题看起来似乎很熟悉，对一个矩阵进行染色，当翻转、旋转、平移相同时认为方案相同，求本质不同的染色方案，好像就是简单的套用Polya计数来求解。但观察发现平移的规则发生了变化，如果某个被染色的格子被移出矩阵，则不允许平移，而不是普通的从反方向进入，这样就不便于将其写成一个置换的形式来进行Polya计数。于是我们跳出用Polya解决此题的的思路，寻找新的光明之道。对，有关置换的计数不是还有一个Burnside引理吗！Burnside引理着眼于方案全集，关键是要计算出在每个置换下保持不动的方案，这在本题中或许不难解决。因为n行m列和m行n列得到的方案数是相同的，不妨设。平移的规则不好用置换来表示，于是不妨修改状态表示，从而避免考虑平移的变换。下面提到的u行v列的矩阵均满足。定义：表示u行v列的矩阵中，在其每条边上都至少有一个格子被染色，其本质不同的染色方案数。因为每条边上都有染色的格子，所以无论向哪个方向平移，都会有染色的格子移出矩阵，所以无法进行平移操作的，那么只需要考虑翻转和旋转了。表示每条边上都至少有一个格子被染色的u行v列的矩阵，总的染色方案数。表示每条边上都至少有一个格子被染色的u行v列的矩阵，其通过旋转180度保持不变的染色方案数。表示每条边上都至少有一个格子被染色的u行u列的矩阵，其通过旋转90度或270度保持不变的染色方案数。表示每条边上都至少有一个格子被染色的u行v列的矩阵，其通过上下翻转保持不变的染色方案数。表示每条边上都至少有一个格子被染色的u行v列的矩阵，其通过左右翻转保持不变的染色方案数。表示每条边上都至少有一个格子被染色的u行u列的矩阵，其通过沿某条对角线翻转保持不变的染色方案数。求得所有的G值，F值就只需套用引理即可。而的求法也都大同小异。就是应用容斥原理，将所有格子任意染色，减去第一行或者第u行或者第一列或者第v列没染色，再加上第1行和第u行均未染色……即：：旋转180度不变，实际上就是前个格子任意染色，然后剩下的格子染色情况则由这些格子旋转得到，同样需要应用容斥原理：：旋转90度或者270度，则是由左上角的个格子任意染色，然后剩下的格子染色情况则由这些格子旋转得到，同样需要应用容斥原理：：上下翻转，则是由上半部分的个格子任意染色，然后剩下的格子染色情况则由这些格子旋转得到，同样需要应用容斥原理：：左右翻转，则是由半边部分的个格子任意染色，然后剩下的格子染色情况则由这些格子旋转得到，同样需要应用容斥原理：：沿对角线翻转，则是由对角线上面部分的个格子任意染色，然后剩下的格子染色情况则由这些格子旋转得到，同样需要应用容斥原理：定义：表示u行1列的矩阵，该行第1行和第u行的格子都被染色，其本质不同的染色方案数。因为只有1列，所以求解只需考虑上下翻转一种置换。应用Burnside引理，得到：而当，则有：对于所有的，其边框上都有被染色的格子，所以不会有重复的计算，所以：利用Burnside引理，圆满解决了该题，F和G都有个状态，其每个状态求解的时间复杂度为，所以算法总的时间复杂度为。因为可以在一边求F函数时，一边求Ans，某个F函数的求解也不依赖于其他F函数来递推，所以无需保存任何