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

· · 题解

博客食用更佳

传送门：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 即可。

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

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

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