P4980 【模闆】Polya定理

polya定理

P4980 【模闆】Polya定理

給定一個\(n\)個點，\(n\)條邊的環，有\(n\)種顔色，給每個頂點染色，問有多少種本質不同的染色方案，答案對\(10^9+7\)取模

注意本題的本質不同，定義為：隻需要不能通過旋轉與别的染色方案相同。

第一行輸入一個\(t\)，表示有\(t\)組資料

第二行開始，一共\(t\)行，每行一個整數\(n\)，意思如題所示。

共\(t\)行，每行一個數字，表示染色方案數對\(10^9+7\)取模後的結果

\(n \leq 10^9,t \leq 10^3\)

注意置換隻有\(n\)個，表示旋轉的度數，沒有翻轉。

那麼一個旋轉\(i\)個點的置換的循環個數應該為\(\gcd(i,m)\)

帶到\(Polya\)定理裡面去，方案數為

\[\frac{1}{n}\sum_{i=1}^n n^{\gcd(i,n)}

\]

\[=\frac{1}{n}\sum_{i=1}^n n^k\sum_{k=1}^n[\gcd(i,n)=k]

\[=\frac{1}{n}\sum_{k\mid n} n^k\sum_{k=1}^n[\gcd(i,n)=k]

\[=\sum_{k\mid n} n^{k-1}\sum_{k=1}^{\frac{n}{k}}[\gcd(i,n)=1]

\[=\sum_{k|n}n^{k-1}\varphi(\frac{n}{k})

然後直接暴力搞，複雜度是常數很小的\(O(Tn^{\frac{3}{4}})\)

Code:

2018.12.21