人有多大胆,暴力多大产

【矩阵加速】【特征根方程】【Polya定理】【欧拉函数】【莫比乌斯反演】[BZOJ3202][SDOI2013]项链

题目大意

给出一个项链,项链上的每个珠子,都是一个三元组$(x,y,z)|0<x\leq y\leq z\leq a$同时$(x,y,z)=1$

如果两个项链可以通过旋转而互相达到,那么这两个项链是相同的,并且项链上的相邻珠子不能取相同的颜色。

给出$n$和$a$求长度为$n$的本质不同的项链有多少条。

简单题解

首先我们不难发现,当我们已经知道了珠子的所有方案数量的时候,我们就可以通过Polya定理进行计数就能得到答案了。

我们将问题分解成了两个部分

  1. 珠子有多少种合法的取的方案数。
  2. 项链有多少种不重叠的方案数量。

Part 1

首先我们考虑将三元组$(x,y,z)$的限制更改一下,更改成无序的,然后我们就可以用简单的莫比乌斯反演在$O(A+T\times \sqrt A)$的时间复杂度内得到珠子的方案数量。

考虑计算$ans_3$表示$x,y,z$的方案

$ans_2$表示$x,y$的方案

这样我们可以通过容斥的原理计算出有序的方案数量,考虑到$x,y,z$互不相同被计算了6次,$x,y$相同被计算了3次,于是我们只要将剩下的三次补齐就行了,三个都相同的也同理

得到$ans=\frac{ans_3+3*ans_2+2}{6}$

Part 2

接下来的第二部分,我们可以考虑一下首先我们枚举项链旋转长度$k$,同时$f(n)$表示长度为$n$的时候的答案。

这样我们就可以得到如下的答案

$$\frac{\sum_{k=0}^n f(gcd(k,n))}{n}$$

为什么呢?首先我们可以考虑对于步长为$k$的移动,显然有$\frac{lcm(k,n)}{k}$即跳跃次数,那么有对于素数$p$

 

假设$p^a|k,p^b|n$

那么最终的指数将会变为$max(a,b)-a=b-min(a,b)$

转化为$\frac{n}{gcd(k,n)}$

最终循环节个数为$gcd(k,n)$个,同时不难发现这$gcd(k,n)$个是相邻排列的,可以根据对称性感性理解,反证法,同余方法均可证明,在此不多做赘述。

然后我们考虑$f$的计算

$$f(1)=0\\f(2)=ans*(ans-1)\\f(i)=f(i-1)*(ans-2)+f(i-2)*(ans-1)$$

然后我们可以使用矩阵加速来进行优化。但是我们发现上述的递推式仍然无法计算

所以我们要对统计答案的式子进行化简

$$\sum_{k=0}^n f(gcd(k,n))=\sum_{p|n}f(p)*phi(\frac{n}{p})$$

最终的复杂度为$O(A+T\times (\sqrt A+\sqrt A \times \log n))$

加入讨论

电子邮件地址不会被公开。 必填项已用*标注