首页 > 代码库 > hdu5080：几何+polya计数（鞍山区域赛K题）
hdu5080：几何+polya计数（鞍山区域赛K题）
/*
鞍山区域赛的K题。。当时比赛都没来得及看（反正看了也不会）
学了polya定理之后就赶紧跑来补这个题。。
由于几何比较烂写了又丑又长的代码，还debug了很久。。
比较感动的是竟然1Y了。。
*/
题目大意：
给定一些点，某些点上有边，问用k种颜色染色的等价类有多少种
思路：
由于坐标是整数。。只有可能旋转90，180，270才能得到置换
且图形必须为中心对称图形
先用几何方法找出对称中心
然后旋转，找是否出现置换。。。
由于点数只有50，几何预处理这一部分可以很暴力无脑的写。。各种判断相等即可
得到置换数和每个置换的循环数之后用polya定理的公式求和即可（取模需要逆元）
代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<math.h>#include<ctype.h>using namespace std;#define esp 0.0000000001#define mod 1000000007bool isequal(double a,double b){ if(fabs(a-b)<esp) return 1; return 0;}struct point{ double x,y; bool operator ==(point a) { return (isequal(x,a.x)&&isequal(y,a.y)); } void rotate(point o) { double y1=y-o.y; double x1=x-o.x; x=o.x+y1; y=o.y-x1; }}O,p[55],q[55];struct edge{ int a,b; bool operator ==(edge t) { return ((p[a]==q[t.a]&&p[b]==q[t.b])||(p[b]==q[t.a]&&p[a]==q[t.b])); }}e[2510];////int g,r[55],n,m,k,rev[5];long long exgcd(long long a,long long b,long long &x,long long &y){ if(a==0&&b==0) return -1; if(b==0){x=1;y=0;return a;} long long d=exgcd(b,a%b,y,x); y-=a/b*x; return d;}//*********求逆元素*******************//ax = 1(mod n)long long inv(long long a,long long n){ long long x,y; long long d=exgcd(a,n,x,y); if(d==1) return (x%n+n)%n; else return -1;}long long quickmod(long long a,long long b,long long m) //a^b%m{ long long res=1; while(b) { if(b&1) res=res*a%mod; b>>=1; a=a*a%mod; } return res;}point mid(point a,point b){ point res; res.x=(a.x+b.x)/2; res.y=(a.y+b.y)/2; return res;}point sym(point a,point o){ point res; double x1=o.x-a.x; double y1=o.y-a.y; res.x=o.x+x1; res.y=o.y+y1; return res;}int yes(int i,int j){ int ok=1; point tmp; for(int i=0;i<n;i++) { tmp=sym(p[i],O); int j; for(j=0;j<n;j++) { if(p[j]==tmp) { break; } } if(j==n) { ok=0; break; } } return ok;}int findo(){ int ok=0; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { O=mid(p[i],p[j]); if(yes(i,j)) { ok=1; break; } } if(ok) break; } return ok;}int check(){ int ok=1; for(int i=0;i<m;i++) { int j; for(j=0;j<m;j++) { if(e[j]==e[i]) { break; } } if(j==m) { ok=0; break; } } return ok;}int findrev(){ int ok=1; for(int i=0;i<n;i++) { int j; for(j=0;j<n;j++) { if(p[i]==q[j]) { r[i]=j; break; } } if(j==n) ok=0; if(ok==0) break; } return ok;}int findloop(){ int res=0; bool vi[55]; memset(vi,0,sizeof(vi)); for(int i=0;i<n;i++) { if(!vi[i]) { for(int j=i;;j=r[j]) { vi[j]=1; if(r[j]==i) { break; } } res++; } } return res;}void reverse(){ rev[0]=n; g=1; if(!findo()) { return; } memcpy(q,p,sizeof(q)); for(int i=1;i<=3;i++) { for(int j=0;j<n;j++) { q[j].rotate(O); } if(check()) { if(findrev()) rev[g++]=findloop(); } }}void ini(){ scanf("%d%d%d",&n,&m,&k); for(int i=0;i<n;i++) { scanf("%lf%lf",&p[i].x,&p[i].y); } for(int i=0;i<m;i++) { scanf("%d%d",&e[i].a,&e[i].b); e[i].a--; e[i].b--; }}void solve(){ reverse(); long long ans=0; for(int i=0;i<g;i++) { ans+=quickmod(k,rev[i],mod); ans%=mod; } if(g==4) { ans*=inv(2,mod); ans%=mod; ans*=inv(2,mod); ans%=mod; } else { ans*=inv(g,mod); ans%=mod; } printf("%I64d\n",ans);}int main(){ //freopen("in.txt","r",stdin); int t; scanf("%d",&t); while(t--) { ini(); solve(); } return 0;}
hdu5080：几何+polya计数（鞍山区域赛K题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。