polya定理

  • 2017-12-25
  • 0
  • 0

好吧,我似乎现在才知道polya定理的式子。。(我好弱啊

orz Amphetamine

f[d]表示不考虑同构的方案数

就是相当于每一个旋转方案,他会有一个gcd(i,n)的循环节,所以我们计算出来这个循环节的方案就好了

然后我们可以枚举每一个gcd,找到gcd为d的个数乘起来就好了,这样复杂度是O(√ n)的

 

评论

还没有任何评论,你来说两句吧