poj 2409+2154+2888（Burnside定理）

三道burnside入门题：

Burnside定理主要理解置换群置换后每种不动点的个数，然后n种不动点的染色数总和/n为answer。

对于旋转，旋转i个时不动点为gcd(n,i).

传送门：poj 2409

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <cstdlib>

#define LL long long

#define N 25

#define mod 1000000007

using namespace std;

LL p[];

int gcd(int a,int b)

{

    return b==?a:gcd(b,a%b);

}

LL power(LL a,LL n)

{

    LL res=;

    while(n)

    {

        if(n&)res*=a;

        a=a*a;

        n>>=;

    }

    return res;

}

int main()

{

    int n,k;

    while(scanf("%d%d",&k,&n)>)

    {

        if(n+k==)break;

        LL ans;

        if(n&)ans=n*power(k,n/+);

        else ans=n/*(power(k,n/)+power(k,n/+));

        for(int i=;i<=n;i++)ans+=power(k,gcd(n,i));

        printf("%lld\n",ans/(*n));

    }

}

传送门：poj 2154

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <cstdlib>

#define LL long long

#define N 35000

#define mod 1000000007

using namespace std;

int n,p;

int prime[N+],tot;

bool vis[N+];

void init()

{

    tot=;

    memset(vis,false,sizeof(vis));

    for(int i=;i<=N;i++)

    {

        if(!vis[i])

        {

            prime[tot++]=i;

        }

        for(int j=;j<tot;j++)

        {

            if(i*prime[j]>N)break;

            vis[i*prime[j]]=true;

        }

    }

}

LL power(LL a,LL n)

{

    LL res=;

    while(n)

    {

        if(n&)res=res*a%p;

        a=a*a%p;

        n>>=;

    }

    return res;

}

LL Phi(int x)

{

    int res=;

    for(int i=;prime[i]*prime[i]<=x&&x>;i++)

    {

        if(x%prime[i]==)

        {

            res*=prime[i]-;

            x/=prime[i];

            while(x%prime[i]==)

            {

                x/=prime[i];

                res*=prime[i];

            }

        }

    }

    if(x>)res*=x-;

    return res;

}

int primefactor[N<<],sz;

void factor(int x)

{

    sz=;

    for(int i=;i*i<=x;i++)

    {

        if(x%i==)

        {

            primefactor[sz++]=i;

            if(i*i!=x)primefactor[sz++]=n/i;

        }

    }

}

LL solve(int n)

{

    factor(n);

    LL ans=;

    for(int i=;i<sz;i++)

    {

        ans=(ans+Phi(n/primefactor[i])*power(n,primefactor[i]-))%p;

    }

    return ans;

}

int main()

{

    int T;init();

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&p);

        printf("%d\n",solve(n));

    }

}

传送门：poj 2888

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <cstdlib>

#define LL long long

#define N 35000

#define mod 9973

using namespace std;

int n,m,k;

int prime[N+],tot;

bool vis[N+];

struct matrix

{

    int m[][];

    void zore()

    {

        memset(m,,sizeof(m));

    }

    void unit()

    {

        for(int i=;i<;i++)

            for(int j=;j<;j++)

            m[i][j]=i==j;

    }

}g;

matrix mult(matrix a,matrix b)

{

    matrix c;

    c.zore();

    for(int k=;k<m;k++)

    for(int i=;i<m;i++)

    {

        if(a.m[i][k]==)continue;

        for(int j=;j<m;j++)

            c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;

    }

    return c;

}

matrix quick_power(matrix a,int n)

{

    matrix res;

    res.unit();

    while(n>)

    {

        if(n&)res=mult(res,a);

        a=mult(a,a);

        n>>=;

    }

    return res;

}

int calc(int n)

{

    int ans=;

    matrix res=quick_power(g,n);

    for(int i=;i<m;i++)

    {

        ans=(ans+res.m[i][i])%mod;

    }

    return ans;

}

void init()

{

    tot=;

    memset(vis,false,sizeof(vis));

    for(int i=;i<=N;i++)

    {

        if(!vis[i])

        {

            prime[tot++]=i;

        }

        for(int j=;j<tot;j++)

        {

            if(i*prime[j]>N)break;

            vis[i*prime[j]]=true;

        }

    }

}

LL Phi(int x)

{

    int res=;

    for(int i=;prime[i]*prime[i]<=x&&x>;i++)

    {

        if(x%prime[i]==)

        {

            res*=prime[i]-;

            x/=prime[i];

            while(x%prime[i]==)

            {

                x/=prime[i];

                res*=prime[i];

            }

        }

    }

    if(x>)res*=x-;

    return res;

}

int primefactor[N<<],sz;

void factor(int x)

{

    sz=;

    for(int i=;i*i<=x;i++)

    {

        if(x%i==)

        {

            primefactor[sz++]=i;

            if(i*i!=x)primefactor[sz++]=n/i;

        }

    }

}

int power(int a,int n)

{

    int res=;

    a%=mod;

    while(n)

    {

        if(n&)res=res*a%mod;

        a=a*a%mod;

        n>>=;

    }

    return res;

}

int solve(int n)

{

    factor(n);

    int ans=;

    for(int i=;i<sz;i++)

    {

        ans=(ans+Phi(n/primefactor[i])*calc(primefactor[i]))%mod;

    }

    return ans*power(n,mod-)%mod;

}

int main()

{

    int T;

    scanf("%d",&T);

    init();

    while(T--)

    {

        scanf("%d%d%d",&n,&m,&k);

        g.zore();

        for(int i=;i<m;i++)

            for(int j=;j<m;j++)

            g.m[i][j]=;

        while(k--)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            u--;v--;

            g.m[u][v]=g.m[v][u]=;

        }

        printf("%d\n",solve(n));

    }

}

巴特西

poj 2409+2154+2888（Burnside定理）

最新文章

热门文章