AquaRio 的博客

AquaRio 的博客

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

posted on 2019-10-09 08:55:33 | under 题解 |

博客食用更佳

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

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

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

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