题解 P2561
gxy001
·
·
题解
看到染色旋转翻转，我们就可以猜到这道题需要使用 Pólya 定理（ ó : Alt + 243 ）。
Pólya 定理
l=\frac 1 {\mid G\mid}\sum_{k=1}^{\mid G \mid}m^{c(p_k)}
## 分析
显然，在此题中 $\mid G \mid=6$，分别为单位元，由旋转得到的两种，由翻转得到的三种，可以观察出既旋转又翻转得到的置换包括在上述六种中。又由黑白染色得出 $m=2$，瓷砖大小 $N=\frac{n\times(n+1)}{2}$。
代入公式，我们可以发现仅剩 $c(p_k)$ 没有求出，思考循环的含义：
$$\bigg(^{a_1\ a_2\ a_3\ \cdots\ a_n}_{a_n\ a_1\ a_2\ \cdots\ a_{n-1}}\bigg)=(1\ 2\ 3\ \cdots\ n)$$
+ 我们可以发现，单位元的循环数量显然为 $N$；
+ 而对于旋转产生的两种置换，一个点在旋转 $120\degree$ 后定然与另一点重合，在旋转三次后回到原位，共经过三个位置，那么每一个循环的大小就为 $3$，循环数量为 $\lceil\frac N 3\rceil$，注意向上取整，原因——在某些情况下（如 $n=4$），存在不动的中心点，其循环大小为 $1$；
+ 对于翻转来说，除了对称轴上的 $\lceil\frac n 2\rceil$ 个点，其余均为两两交换，循环大小为 $2$，循环数量为 $\frac {N-\lceil\frac n 2\rceil} 2+\lceil\frac n 2\rceil$。
## 结论
$$
ans=\frac 1 6(2^N+2\times 2^{\lceil\frac N 3\rceil}+3\times2^{(\frac {N-\lceil\frac n 2\rceil} 2+\lceil\frac n 2\rceil)})
$$
$$N=\frac{n\times(n+1)}{2}$$
## 代码
注意：此题需要高精度，但可以不用快速幂。
```cpp
#include<cstdio>//for IO
#include<cstring>//for memset
#include<utility>//for std::swap
int n,bs,xz,fz;//单位元，旋转，翻转
struct bign{
static const int base=10000;
int a[60],l;
bign():l(){//init
memset(a,0,sizeof(a));
}
int& operator [](int x){
return a[x];
}
const int& operator [](int const&x)const{
return a[x];
}
friend bign operator + (bign x,bign y){
bign ans;
if(x.l<y.l)std::swap(x,y);
ans[0]=0;
for(ans.l=0;ans.l<x.l||ans[ans.l];++ans.l){
ans[ans.l]+=x[ans.l]+y[ans.l];
if(ans[ans.l]>base)ans[ans.l+1]=1,ans[ans.l]-=base;
else ans[ans.l+1]=0;
}
return ans;
}
friend bign operator *(bign x,int y){
bign ans;
ans[0]=0;
for(ans.l=0;ans.l<x.l||ans[ans.l];++ans.l){
ans[ans.l]+=x[ans.l]*y;
if(ans[ans.l]>base)ans[ans.l+1]=ans[ans.l]/base,ans[ans.l]%=base;
else ans[ans.l+1]=0;
}
return ans;
}
friend bign operator /(bign x,int y){
for(int i=x.l-1;~i;--i){
if(i)x[i-1]+=(x[i]%y)*base;
x[i]/=y;
}
while(x.l&&!x[x.l-1])x.l--;
return x;
}
void output(void){
printf("%d",a[l-1]);
for(int i=l-2;~i;--i)
printf("%04d",a[i]);
}
}bsp,fzp,xzp,res;
int main(){
scanf("%d",&n);
bs=n*(n+1)/2;
fz=(bs-(n+1)/2)/2+(n+1)/2;
xz=(bs+2)/3;
//ans=(pow(2,bs)+pow(2,fz)*3+pow(2,xz)*2)/6
bsp[0]=1,bsp.l=1;
for(int i=1;i<=bs;i++)bsp=bsp*2;
fzp[0]=1,fzp.l=1;
for(int i=1;i<=fz;i++)fzp=fzp*2;
fzp=fzp*3;
xzp[0]=1,xzp.l=1;
for(int i=1;i<=xz;i++)xzp=xzp*2;
xzp=xzp*2;
res=(bsp+fzp+xzp)/6;
res.output();
return 0;
}
```
最后，如有错误，请在评论指出。