bestcoder #88 || hdu 5908 Abelian Period(暴力)

题目链接

题意:一段数字串,如果一个数字k满足,将该串分成若干个长度为K的子串,这些子串两两满足每个字符出现的次数一样多,那么称为k是一个阿贝尔周期。现在问所有合法的阿贝尔周期。

思路:

  • 首先我们发现,所有的阿贝尔周期一定是数字串长度(设为n)的因数。
  • 然后我们还发现。。。如果某个因子是阿贝尔周期,那么该因子的整数倍中恰好也是n的因子的也一定是阿贝尔周期,类似筛法。
  • 然后我们还发现。。。最小的阿贝尔周期一定比数字串中的元素个数大。。。

 

2016-10-02-00-07-21-%e7%9a%84%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be

然而其实后面两个不管也可以过吧。。。因为有点忘了n的约数个数的上界了。。。。

还是太保守了。。。

不过hack了四发哈哈哈。。。要是大号的话今天就紫了呜呜呜

2016-10-01-21-11-30-%e7%9a%84%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz