自动搬运

查看原文

来自洛谷，原作者为

	AquaRio 青鸟终将飞越那道彩虹的彼端， 所以我们也一定能够做到。

搬运于2025-08-24 21:34:39，当前版本为作者最后更新于2019-10-09 08:55:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

博客食用更佳

传送门：P2162

Description

给出一个有 $n$ 个点的圆环，现在要用 $17$ 种不同的颜色填充它。 若两种填色方案经过旋转后可以重合，则视这两种填色方案为同一种填色方案。 保证 $17$ 种颜色通必须用上。 求方案数，答案保留最后 $120$ 位，不够的用 $0$ 补齐。

前言

管理员大大请把这个题改为黑题。
这个题看起来好难啊，于是我们上网搜索题解。
没想到它涉及群论，容斥，高精。为什么是蓝题啊
那我们就来研究一下这道题吧

Solution

由于 $n$ 个点组成的圈可以形成 $n$ 个置换，显然有循环节数为 $\gcd (i,n)$ ，单个循环节长度为 $\frac{n}{\gcd (i,n)}$

设仅用 $m$ 种颜色染色的方案为 $f(m)$。

由Burnside引理和Polya定理可得

$$f(m)=\frac{\sum_{i=1}^{n} m^{\gcd (i,n)} }{n}$$

把 $n$ 移过来，将 $\gcd$ 移出来，也就是枚举 $\gcd$ ：

$$f(m) \times n = \sum_{i|n} m^i \times \sum_{j=1}^n [\gcd (n,j)==i] $$$$f(m) \times n = \sum_{i|n} m^i \times \sum_{j=1}^{\frac{n}{i}} [\gcd (n,i \times j)==i] $$$$f(m) \times n = \sum_{i|n} m^i \times \sum_{j=1}^{\frac{n}{i}} [\gcd (\frac{n}{i}, j)==1] $$$$f(m) \times n = \sum_{i|n} m^i \times φ (\frac{n}{i}) $$

考虑 $n<=10^9$ 我们可以暴力分解，枚举质因数。记得写高精。

因为17种颜色都要用到，用容斥：

$$Ans=\sum_{m=1}^{17} (-1)^{m+1} \times f(m) \times C_{17}^m $$

需要注意的一点是，要求出 $f(m)$ ，我们要做一个高精除法。可以把每一个高精度数保存为 $q\times n+p$ 的形式。

换言之，就是把最后一位的十进制改成 $n$ 进制，最后答案直接输出 $q$ 即可。

高精还要压位，不然会被卡常。

所以这是一道群论裸题，但是毒瘤出题人搞出了一堆恶心操作。

代码就自己写吧 （你都能看完这篇题解了当然能写代码了吧