程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [codevs 2926] 黑白瓷磚(2002年安徽省隊選拔賽)

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

編輯:關於C++

 


題解:

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<
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved