[POJ 2888]

Magic Bracelet

数论。

本来这题是在分类表里靠后的位置的,但由于最近在啃具体数学,第四章讲了“莫比乌斯反演”,就顺势把题做一下。

题意是这样的,有一个长度为n的珠串,每个珠子的颜色有m种,但其中有k对颜色是不能相邻的,问在剔除因旋转导致的重复后总共有多少种可能的珠串。

先讲这题的简化版,是POJ 2154,区别在于没有珠子间不能连接的限制。

其基本的思想仍然是Polya定理。但是这里由于n值太大,无法直接枚举出所有的置换群。于是需要考虑将具有相同数量循环节的置换群合并处理。具体的合并方式是要利用到欧拉函数phi()的性质的。总共的置换群有n个,对n的每个因子d,有n/d个循环节的置换群其每个循环节长度为d,而这样的循环群总数是phi(d)个。又因为欧拉函数满足sum_{d\n} phi(d) == n,因此计数式子就可以转化为 (sum_{d\n} phi(d) * n^(n/d)) / n。计算phi(d)的时间复杂度是O(lgd),而n的因子总数是不超过1000的(最多9个不同因子),n的n/d次方是可以在O(lg(n/d))时间内计算得到的,由此问题便能在合理时间内求解了。

另外就是计算的时候,要注意利用模运算的性质,使用int来处理(比long long快很多),同时尽量减少进行模运算的次数,否则还是会TLE的。

下面是2154的代码:

回到2888。这题额外增加了珠子间的连接限制,对应的处理方式是这样的:初始化矩阵a[m][m]元素全为1,若i和j不能相邻,则a[i][j]=a[j][i]=0,然后计算b = a^d,则长度为d的珠串其总可能数是sum{b[i][i]}。这里当i<=j时,(a^d)[i][j]表示的是,以种类i开始长度为d,结尾能够与种类j的珠子相连的珠串总数。至于为什么是这样,推一下就明白了。 于是这里计数式子就变成了(sum_{d\n} phi(d) * sum{(a^(n/d))[i][i]}) / n。 落实到具体实现时,在对n做除法时,要转化成乘以模运算下n的乘法逆元。前面的每一步处理也要控制好在int的范围内以及限制模运算的使用次数。

虽然上面写了这么多但很多都是现学现卖的OTL。不过数论还真是很有意思的东西……