自动搬运

查看原文

来自洛谷，原作者为

	gxy001 ......

搬运于2025-08-24 21:39:05，当前版本为作者最后更新于2020-08-13 11:25:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

看到染色旋转翻转，我们就可以猜到这道题需要使用 Pólya 定理（ ó : Alt + 243 ）。

Pólya 定理

$$l=\frac 1 {\mid G\mid}\sum_{k=1}^{\mid G \mid}m^{c(p_k)} $$

$G=\{p_1,p_2,\cdots\}$ 为 $N$ 个对象的置换群，$c(p_k)$ 为置换 $p_k$ 的循环数，$l$ 为 $m$ 种颜色染 $N$ 个对象的方案数。

分析

显然，在此题中 $\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}$$

代码

注意：此题需要高精度，但可以不用快速幂。

#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;
}

最后，如有错误，请在评论指出。