HDU 3547 DIY Cube 數論- Polya定理

給定正方體，要求給正方形的八個頂點著色，問有多少種不同的著色方案，當然通過旋轉和翻轉得到的著色方案視為相同。

這題是一道典型的Polya定理的題目，根據polya定理，可以直接求得公式。

①單位元素(1)(2)(3)(4)(5)(6)(7)(8)，格式為(1)^8。
②繞過xx'軸旋轉±90°的置換分別為(1 2 3 4)(5 6 7 8), (4 3 2 1)(8 7 6 5) ,格式為(4)^2，同類的置換有6個。
③繞xx'軸旋轉180°的置換為(1 3)(2 4)(5 7)(6 8)，格式(2)^4，同類的置換有3個。

④繞yy'軸旋轉180 °的置換為(1 7)(2 6)( 3 5 )(4 8)格式為(2)^4，同類的置換有6個。

⑤繞zz'軸旋轉±120°的置換分別為(8 3 6)(4 2 5) (1)(7)          (6 3 8)(5 2 4) (1)(7)格式為(3)^2 (1)^2，同類的置換有8個

從而對於給定的輸入N，得到的答案是(n^8+17*n^4+6*n^2)/24.

因為數據比較大，用java寫。

代碼如下：

import java.io.*; 
import java.util.Scanner; 
import java.math.BigInteger; 
public class Main 
{ 
    public static void main(String[] args) 
    { 
        Scanner cin=new Scanner(System.in); 
        BigInteger sum,n,m,a=BigInteger.ONE,b=BigInteger.ONE,c=BigInteger.ONE; 
        int cas; 
        BigInteger q=new BigInteger("17"); 
        BigInteger p=new BigInteger("6"); 
        BigInteger r=new BigInteger("24"); 
        BigInteger mm=new BigInteger("1000000000000000"); 
        cas=cin.nextInt(); 
        int i; 
        String aa,bb; 
        for(i=1;i<=cas;i++) 
        { 
            n=cin.nextBigInteger(); 
            int j; 
            a=BigInteger.ONE;b=BigInteger.ONE;c=BigInteger.ONE; 
            for(j=1;j<=8;j++) 
               b=b.multiply(n); 
            a=a.multiply(n); 
            a=a.multiply(n); 
            a=a.multiply(p); 
            c=c.multiply(n); 
            c=c.multiply(n); 
            c=c.multiply(n); 
            c=c.multiply(n); 
            c=c.multiply(q); 
            a=a.add(b); 
            a=a.add(c); 
            a=a.divide(r); 
            aa=a.toString(); 
            bb=mm.toString(); 
            int len=aa.length(); 
            if(aa.length()<=15) 
            { 
               System.out.println("Case "+i+": "+aa); 
            } 
            else 
            { 
               System.out.print("Case "+i+": "); 
               for(j=len-15;j<len;j++) 
               { 
                    System.out.print(aa.charAt(j)); 
               } 
               System.out.println(); 
            } 
        } 
    } 
}