poj 1286 ploya.txt

一些数论题目的代码

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iterator>
using namespace std;

#define INFI 9999999
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back

//POJ 1286 ploya
//如果结果过大、double精度不够就换用int64或者long long，并且自己写对应整数的pow比较保险
//如果还不够用，就自己写高精度吧
#define NMAX 99
//int b1[NMAX],b2[NMAX];
//bool bj[NMAX];

__int64 ppow(__int64 c,__int64 x)
{
	__int64 ans=1;
	while(x>0) {ans*=c;x--;}
	return ans;
}

__int64 ploya1(__int64 c,__int64 n)//旋转和翻转视为相同,poj 1286用这个函数过的
{
	bool b1[NMAX],b2[NMAX];
       __int64 i,j,k,x,y;
       __int64 t=0;
	   if(n==0) return 0;
       for (i=0;i<=n-1;i++)
       {
		     memset(b1,0,sizeof(b1));
			 memset(b2,0,sizeof(b2));
             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+ppow(c,x)+ppow(c,y);
       }
       return t/(2*n);
}

/*
int lala(int a,int b,int c)
{
	if(a==0 && b==0) return c;
	else if(a==0 || b==0) return c-1;
	else if(a==b) return c-1;
	else return c-2;
}
*/
/*
int ploya1(int c,int n)//旋转和翻转视为相同
{
       int i,j,k,x,y,q,p;
       double t=0.0;
       for (i=0;i<=n-1;i++)
       {
		       memset(b1,0,sizeof(b1));
			  memset(b2,0,sizeof(b2));
			  q=c+1;
			  p=1;
             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]=i+1;
							   if(q>lala((k-1)%n,(k+1)%n,c)) q=lala(b1[(k-1+n)%n],b1[(k+1)%n],c);
						 }
                   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]=i+1;
							   if(q>lala((k-1)%n,(k+1)%n,c)) q=lala(b2[(k-1+n)%n],b2[(k+1)%n],c);
						 }
					p=p*q;
             }
             t=t+p;
       }
       return t/(2*n);
}
*/
/*
int ploya2(int c,int n)//旋转视为相同，翻转为异
{
       int i,j,k,x,y;
	   bool bj[NMAX];
       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;
}

int ploya3(int c,int n)//翻转视为相同，旋转为异
{
       int x=n/2;
       if (n%2)       x++;
       return (pow(c,n)+pow(c,x))/2;
}
*/
int main()
{
	__int64 n;
	scanf("%I64d",&n);
	while(n!=-1)
	{
		printf("%I64d\n",ploya1(3,n));
			scanf("%I64d",&n);
	}
	return 0;
}