hdu 1812 Count the Tetris （置换）

题目描述

传送门

题目大意： 用c种颜色给一个n*n的矩阵染色，问有多少种本质不同的方案。即旋转，翻转后相同的算同一种方案。

题解

不想写高精度，所以就直接找标算拍了拍小数据。。。。 先引入置换常用的两个引理： Burnside引理：记 C(f) 为在置换 f 下保持不变的着色方案数，本质不同的着色方案数为所有置换f的C(f)值的平均数。 设置换群 G 作用于有限集合X上，则 X 在G作用下的等价类的数目为:

N=1|G|∑g∈GX(g) 其中 X(g) 为 g 在X上的不动点个数，即满足 g(a)=a 的个数.

不过大多数情况下我们都不需要用Burnside引理，而要用Polya定理。 Polya定理：设 G 是p个对象的一个置换群，用k种颜色涂染这p个对象，若一种染色方案在置换群 G 的作用下变成了另一种方案，则这两个方案当做是同一种方案，这样不同染色方案为： l=1|G|∑f∈Gkm(f) 其中 m(f) 为置换 f 的循环节数。

那么我们现在回到这个题。对所有置换的情况进行分类讨论。 （1）沿对称轴上下折叠，左右折叠（两种方式是相同的） 我们现在要求m(f)，如果n为奇数那么对称轴上的点是不变的，剩下的点是两两之间进行交换，所以 m(f)=(n∗n−n)/2+n ;如果n为偶数那么就是对称轴两边的一一对应， m(f)=n∗n/2 （2）沿对角线折叠，两条对角线。 对角线上的点不变，其他的两两对称。 （3） 旋转0°，那么相当于每个位置意义对应，所以 m(f)=n∗n （4）旋转90°，180°，270°.这个如果是一个n个位置的环形，我们旋转i位的话，循环的个数是gcd(n,i),每个轮换的长度为n/gcd(n,i) .对于这个正方形来说我们可以把他拆成一圈一圈的形式，分别计算并累加。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 37 using namespace std; int a[N][N],b[N*N],pos[N*N],n,m,c,use[N*N],ans; int quickpow(int num,int x) { int ans=1; int base=num; while (x) { if (x&1) ans=base*ans; x>>=1; base=base*base; } return ans; } int gcd(int x,int y) { if (x<=0||y<=0) return 0; int r; while (y) { r=x%y; x=y; y=r; } return x; } int main() { freopen("a.in","r",stdin); freopen("my.out","w",stdout); scanf("%d%d",&n,&c); m=n*n; if (n%2==0) ans+=quickpow(c,m/2)*2;//上下左右折叠 else ans+=quickpow(c,(m-n)/2+n)*2; ans+=quickpow(c,(m-n)/2+n)*2;//沿对角线折叠 int cnt=0; for (int i=n-1;i>=0;i-=2) if (i==0) cnt++; else cnt+=gcd(4*i,i); ans+=quickpow(c,cnt); cnt=0; for (int i=n-1;i>=0;i-=2) if (i==0) cnt++; else cnt+=gcd(4*i,i*2); ans+=quickpow(c,cnt); cnt=0; for (int i=n-1;i>=0;i-=2) if (i==0) cnt++; else cnt+=gcd(4*i,i*3); ans+=quickpow(c,cnt); cnt=0; ans+=quickpow(c,m); printf("%d\n",ans/8); }