您的位置: 首页  >  IT文章  >  hdu5080：几何+polya计数（鞍山区域赛K题）

hdu5080：几何+polya计数（鞍山区域赛K题）

分类: IT文章 • 2023-11-25 11:48:31

/*

鞍山区域赛的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 1000000007
bool 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
",ans);
}
int main()
{
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ini();
        solve();
    }
    return 0;
}

相关推荐