[HDU1812]Count the Tetris（置换群）

2019-11-08 00:50:27

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

根据Polya定理设G $G$ 是p $p$ 个对象的一个置换群，用k $k$ 种颜色染这p $p$ 个对象，若一种染色方案在群G $G$ 的作用下变为另一种方案，则这两个方案当做是同一种方案，这样不同染色方案数为l=1|G|∑f∈Gkm(f) $l={1/over |G|}/sum/limits_{f/in G}k^{m(f)}$ 其中m(f) $m(f)$ 为p $p$ 的循环节数。

还有一个结论：n个珠子串成环状，顺时针旋转i格的置换中，循环的个数为gcd(n,i) $gcd(n,i)$ ，每个循环的长度为ngcd(n,i) $n/over gcd(n,i)$

也就是说，解决这道题的方法是，对于群中的每一个置换，计算出这个置换的循环节数，然后对k做幂运算相加，最后求平均值对于这道题来说，一共有8个置换，其中4个翻转，4个旋转，对于这8种置换分别求循环节数正向翻转：若上下翻转，若n为奇数，对于每一行来说，循环节长度为1的有一个，循环节长度为2的有⌊n2⌋ $/lfloor{n/over 2}/rfloor$ 个，所以总共有(⌊n2⌋+1)∗n $(/lfloor{n/over 2}/rfloor+1)*n$ 个；若n为偶数，对于每一行，循环节长度为2的有n2 $n/over 2$ 个，所以总共有n∗n2 $n*n/over 2$ 个；左右翻转和上下翻转相同。斜向翻转：对角线循环节长度为1，另外两边对应，共有n+n∗n−n2 $n+{n*n-n/over 2}$ 个；左上右下和右上左下相同，所以总共为2∗(n+n∗n−n2) $2*(n+{n*n-n/over 2})$ 个。旋转：分为旋转0°，90°，180°，270°，这个时候就可以用上面的结论，先计算出每一层的点的个数，然后计算旋转的个数，用gcd计算循环节的个数最后将答案/8

这题我并没有提交，懒得写高精度了…

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define LL long longLL n,k,a,now,ans;LL gcd(LL a,LL b){ if (!b) return a; else return gcd(b,a%b);}LL fast_pow(LL a,LL p){ LL ans=1; for (;p;p>>=1,a*=a) if (p&1) ans*=a; return ans;}int main(){ while (~scanf("%d%d",&n,&k)) { if (n==1LL) {PRintf("%d/n",k);continue;} ans=0LL; //上下左右 if (n&1LL) { now=n*(n/2LL+1LL); ans+=2LL*fast_pow(k,now); } else { now=n*(n/2LL); ans+=2LL*fast_pow(k,now); } //斜 now=n+(n*n-n)/2LL; ans+=2LL*fast_pow(k,now); // 0 now=n*n; ans+=fast_pow(k,now); // 90 now=0LL;a=n; while (a>1LL) { LL t=gcd(4LL*(a-1LL),a-1LL); now+=t; a-=2LL; } if (n&1) ++now; ans+=fast_pow(k,now); // 180 now=0LL;a=n; while (a>1) { LL t=gcd(4LL*(a-1LL),2LL*(a-1LL)); now+=t; a-=2LL; } if (n&1) ++now; ans+=fast_pow(k,now); // 270 now=0LL;a=n; while (a>1) { LL t=gcd(4LL*(a-1),3LL*(a-1)); now+=t; a-=2LL; } if (n&1) ++now; ans+=fast_pow(k,now); printf("%I64d/n",ans/8LL); }}

上一篇：解决你的乱码难题（Qt转码与char和utf8的互转）

下一篇：使用 springMVC 请求Action 返回400编码

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注