Ploya定理学习笔记

由于自己的作息极其不规律导致比赛被打爆了但是有的时候状态其实还行。

关于Ploya定理其实特别有意思这里粘一个[dalao的blog](https://blog.csdn.net/lyc1635566ty/article/details/52545355)

以后有时间了我再写Ploya定理的证明吧。

LINK：[POJ Color](http://poj.org/problem?id=2154)

题目大意：给一个长度为n的项链用n种颜色进行染色项链可以旋转求有多少种本质不同的方案数。

怎么说，ploya裸题显然一共有n种置换每种置换之中循环节的个数是多少呢？

经过不断试验发现对于旋转i个位置的置换循环节个数为gcd(i,n);

于是本质不同的方案数$L=\frac{1}{|G|}\sum{n^{gcd(i,n)}}$

但是$n\leq 1000000000$ 且有T组询问$T\leq 3500$

我们暴力显然是过不了的考虑一番特殊性质设$d=gcd(i,n)$那么显然有d|n d一定是n的因数我们知道n的因数的数量级有$\sqrt{n}$

所以我们要是可以先办法对于$\sqrt{n}$这么多个因数各自算出数量显然也是可以得到答案的。

那么现在存在一个子问题 $\sum_{i=1}^{n}{gcd(i,n)}$ 这个东西怎么求.

这是一个非常经典的问题了，这等价于 $\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}{d\cdot [gcd(i,\frac{n}{d})=1]}$

好像推不下去了其实这个时候该反演了...我们莫比乌斯反演一下

$\sum_{k|n}\mu(k)\sum_{d|\frac{n}{k}}\frac{n}{k}$

我也无能为力了推到死胡同了...自闭。

那么我们从另一个方面再继续推 $\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}{d\cdot [gcd(i,\frac{n}{d})=1]}$

我们发现后面那个东西其实是欧拉函数那么上式=$\sum_{d|n}d\cdot \phi(\frac{n}{d})$

这里我们暴力枚举d 再暴力算$\phi(\frac{n}{d})$肯定会T

不妨将n质因数分解了然后接爆搜因数这样计算欧拉函数会快很多很多复杂度sqrt(n)+1000左右不算很高.

当然还有一种异常靠谱的方法这里给出[blog链接](https://www.cnblogs.com/zhchoutai/p/8450361.html) 不太懂这种方法.

回归到原题上求: $L=\frac{1}{|n|}\sum{n^{gcd(i,n)}}$ 其实就就是 d变成了 $d^{n-1}$罢了 (爆搜可行..

巴特西