[codevs 2926] 黑白瓷磚(2002年安徽省隊選拔賽)

[codevs 2926] 黑白瓷磚(2002年安徽省隊選拔賽)

題解：

Polya定理的應用。
由於第一次做polya定理的題，故要寫的詳細些。
首先可以從題目中讀到三個置換以及一個不動置換：

順時針旋轉120度。 順時針旋轉240度。 左右翻轉180度。 旋轉0度。（不動置換）

開始我本以為這樣就算完成任務，就拿polya定理演算了一遍，結果發現n=2，n=3都不對。後來才明白現在的置換群中不滿足封閉性。比如先順時針旋轉再左右翻轉後的圖形就不包含在內。所以還要增加兩個斜向的翻轉。

現在可以統計每個置換中循環的個數了：

旋轉操作，可以畫圖數學歸納一下，每個循環中都有3個元素，（因為120度是360度的三分之一），那麼一共就有（（點數+2）/ 3）個循環。設為x。 翻轉操作，經歸納，中軸線上有（n+1）/ 2 個點，每個點單獨構成一個循環，其余兩兩配對，所以這些單點少算了一次，總循環數即 （總點數+中軸線上的點數）/ 2。設為y。 不動置換，即總點數。設為z。

接下來根據polya定理求最終結果。因為旋轉有兩個置換，翻轉有三個（左右、斜向兩個），還有一個不動置換，所以最後結果是
ans=2∗2x+3∗2y+2z6

代碼：

其實需要高精，但我沒打。

#include
using namespace std;

int main() 
{
    int n;
    scanf(%d, &n); //底層點數 
    int s = n * (n + 1) / 2; //總點數 
    int m = (s + (n + 1) / 2) / 2; //一個翻轉置換的循環數 
    printf(%d
, (2*(1<<((s+2)/3)) + 3*(1<