polya.cpp

acm 常用算法和代码库

#include <memory.h>
#include <math.h>
#include <iostream>
using namespace std;

int ploya1(int c,int n)//旋转和翻转视为相同
{
       int b1[10000];
       int b2[10000];
       int i,j,k,x,y;
       int t=0;
       memset(b1,0,sizeof(b1));
       memset(b2,0,sizeof(b2));
       for (i=0;i<=n-1;i++)
       {
             for (x=y=j=0;j<=n-1;j++)
             {
                   if (!b1[(i+j)%n])
                         for (x++,k=(i+j)%n;!b1[k];k=(i+k)%n)
                               b1[k]=true;
                   if (!b2[n-1-(i+j)%n])
                         for (y++,k=n-1-(i+j)%n;!b2[k];k=n-1-(i+k)%n)
                               b2[k]=true;
             }
             t=t+pow(c,x)+pow(c,y);
       }
       return t/(2*n);
}

double ploya2(int c,int n)//旋转视为相同，翻转为异
{
       int bj[10000];
       int i,j,k,x,y;
       double t=0.0;
      
       for (i=0;i<=n-1;i++)
       { 
             memset(bj,0,sizeof(bj));
             for (x=y=j=0;j<=n-1;j++)
                   if (!bj[(i+j)%n])
                         for (x++,k=(i+j)%n;!bj[k];k=(i+k)%n)
                               bj[k]=true;
             t=t+pow(c,x);
       }
       return t/n;
}

double ploya3(int c,int n)//翻转视为相同，旋转为异
{
       int x=n/2;
       if (n%2)       x++;
       return (pow(c,n)+pow(c,x))/2;
}



int main()
{
    int a;
    double res;
    
    
    while(cin>>a)
    cout<<ploya2(3,a)<<endl;
    system("pause");
}