HDU5080 简单题，主要是暴力搞出置换群有哪几个，然后polya计数。

Colorful Toy

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 30 Accepted Submission(s): 11

Problem Description

A toy is made up of N vertices and M undirected edges in the 2D plane. As usual, you want to know how many ways there are to color the vertices of the toy. You have totally C colors. And of course, to make things fun, you think that if one color configuration can be rotated to get another, these two configurations should be considered the same. Rotation means 2D in-plane rotation and reflection is not considered as rotation.

For instance, consider coloring the following toy with 2 colors. The coordinates of the vertices are: 1. (0,0) 2. (1,0) 3. (0,1) 4. (-1,0) 5. (0,-1) The toy has 6 edges: (1,2), (1,3), (2,3), (3,4), (4,5), (5,2). As a 2D being, this toy has no symmetry. So there are 32 ways to color it. Had the first two edges been removed, there would be only 12 different ways. You should output the answer modulo 109 + 7.

Input

The first line contains an integer T (T ≤ 20) denoting the number of the test cases. Each test case begins with three positive integers N (1 ≤ N ≤ 50), M (0 ≤ M ≤ N (N - 1)/2) and C(1 ≤ C ≤ 100). Then follow N lines. Each line contains 2 integers in range [-10000,10000] describing a vertex. Then follow M lines. Each line contains 2 integers in range [1,N] representing an edge. There are neither duplicate edges nor self-loops.

Output

For each test case, output one line containing the answer.

Sample Input

2 5 6 2 0 0 1 0 0 1 -1 0 0 -1 1 2 1 3 2 3 3 4 4 5 5 2 5 4 2 0 0 1 0 0 1 -1 0 0 -1 2 3 3 4 4 5 5 2

Sample Output

32 12

Source

2014 Asia AnShan Regional Contest

虽然说旋转的角度是90度的倍数，但是我没有管这个。   我就是粗暴的计算几何的方法进行搞！ 先求平均值，确定中心。 如果和中心重合的点，另外搞出来，其余的点按照极角排序，然后角度相同，按照距离排序。 然后变换的时候肯定是递推过去的。   然后进行判断，一个是判断点可以重合，一个是判断边。 然后就搞定了。

/* ***
Author :kuangbin
Created Time :2014/10/22 21:46:23
File Name :E:\2014ACM\2014现场赛\鞍山\K.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const double eps = 1e-8;
int sgn(double x){
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
struct Point{
double x,y;
double alph;
Point(double _x = 0,double _y = 0){
x = _x;
y = _y;
}
void input(){
scanf(“%lf%lf”,&x,&y);
}
bool operator ==(Point b)const{
return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
}
Point operator -(const Point &b)const{
return Point(x-b.x,y-b.y);
}
double distance(Point p){
return hypot(x-p.x,y-p.y);
}
Point rotate(Point p,double angle){
Point v = (this) - p;
double c = cos(angle), s = sin(angle);
return Point(p.x+v.x\c-v.y*s,p.y+v.x*s+v.y*c);
}
};
long long inv(long long a,long long m){
if(a == 1)return 1;
return inv(m%a,m)(m-m/a)%m;
}
const int MOD = 1e9+7;
long long pow_m(long long a,long long n){
long long ret = 1;
long long tmp = a%MOD;
while(n){
if(n&1)ret = rettmp%MOD;
tmp = tmp*tmp%MOD;
n >>= 1;
}
return ret;
}
Point p[100];
Point center;
int n;
int g[55][55];
vectorV;
bool cmp(int i,int j){
if(sgn(p[i].alph - p[j].alph) != 0)
return p[i].alph < p[j].alph;
else return center.distance(p[i]) < center.distance(p[j]);
}
int link[55];
bool check1(){
double jiao = p[link[V[0]]].alph - p[V[0]].alph;
int sz = V.size();
for(int i = 0;i < sz;i++){
Point tmp = p[V[i]].rotate(center,jiao);
if(tmp == p[link[V[i]]])continue;
return false;
}
return true;
}
bool check2(){
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
if(g[i][j] != g[link[i]][link[j]])
return false;
return true;
}
bool used[100];
int calc(){
int cnt = 0;
memset(used,false,sizeof(used));
for(int i = 0;i < n;i++)
if(!used[i]){
cnt++;
int tmp = i;
while(!used[tmp]){
used[tmp] = true;
tmp = link[tmp];
}
}
return cnt;
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int m,C;
scanf(“%d”,&T);
while(T–){
scanf(“%d%d%d”,&n,&m,&C);
for(int i = 0;i < n;i++)
p[i].input();
int u,v;
memset(g,0,sizeof(g));
while(m–){
scanf(“%d%d”,&u,&v);
u–;
v–;
g[u][v] = g[v][u] = 1;
}
if(n == 1){
printf(“%d\n”,C);
continue;
}
center.x = 0;
center.y = 0;
for(int i = 0;i < n;i++){
center.x += p[i].x;
center.y += p[i].y;
}
center.x /= n;
center.y /= n;
V.clear();
for(int i = 0;i < n;i++){
if(p[i] == center){
link[i] = i;
continue;
}
V.push_back(i);
p[i].alph = atan2(p[i].y-center.y,p[i].x-center.x);
}
sort(V.begin(),V.end(),cmp);
long long ans = 0;
int cnt = 0;
int sz = V.size();
for(int i = 0;i < sz;i++){
for(int j = 0;j < sz;j++)
link[V[j]] = V[(j+i)%sz];
if(!check1())continue;
if(!check2())continue;
ans += pow_m(C,calc());
ans %= MOD;
cnt++;
}
ans = ans*inv(cnt,MOD)%MOD;
printf(“%d\n”,(int)ans);
}
return 0;
}