正三角形涂色

Time Limit: 1 Sec Memory Limit: 128 MB
有如下图所示的正三角形,需要在顶点上涂色,一共共有m种颜色。问一共可以得到多少种不同的涂色方案。如果涂过色的正三角形,经过中心的旋转或沿对称轴的翻转后变成另一个正三角形,那么这两个三角形就认为有同一种涂色方案。
现在告诉你m的数目,请你算算到底有多少种不同的正三角形涂色方案?
正三角形

Input

有多组测试数据。每组测试数据由一个正整数m(m&lt:100),表示颜色数。

Output

对于每组测试数据,在一行里输出不同的涂色方案数。

Sample Input

1
2
2
3

Sample Output

1
2
4
10

题解

诸如用c种颜色给n个珠子的项链染色的问题都可以应用Polya定理
首先,要记住有两种情况
根据题意一种是旋转,一种是翻转
旋转需要记住公式:将环顺时针旋转i格后,循环节个数为gcd(n,i), 染色方案为 ∑c^gcd(n,i) 其中 i=1,2,3,4,….n
翻转分奇偶:
奇数时:染色方案为 n×c^(n/2+1)
偶数时:(n/2)×c^(n/2+1)+(n/2)×c^(n/2)
最后把所有方案加起来除以(2×n)就是最后的答案

AC code:(不包含输入类)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.*;  
import java.util.*;
public class Main {
static long[]pow;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int m=sc.nextInt();
pow=new long[10000]; //先把每一次的幂存下来重复使用
pow[0]=1;
for(int i=1;i<=3;i++){ //计算幂次
pow[i]=pow[i-1]*m;
}
long ans=0;
ans=ans+rotat(); //加上旋转的方案数
ans=ans+overturn(); //加上翻转的方案数
System.out.println(ans/2/3); //除以(2*n)
}

}
static long rotat()
{
long ans=0;
for (int i=0;i<3;i++)
ans=ans+pow[gcd(i,3)]; //∑c^gcd(n,i)
return ans;
}
static int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b); //扩展欧几里得
}
static long overturn()
{
long ans=0;
ans=ans+3*pow[(3+1)/2]; //因为n=3是奇数
return ans;
}
}