题解 P2162 【[SHOI2007]宝石纪念币】

[博客食用更佳](http://39.105.95.125/index.php/archives/416/) **传送门**：[P2162](https://www.luogu.org/problem/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$ 即可。 高精还要压位，不然会被卡常。 所以这是一道群论裸题，但是毒瘤出题人搞出了一堆恶心操作。 代码就自己写吧 ~~（你都能看完这篇题解了当然能写代码了吧~~