Description

问长度为N，字符集大小为K的字符串中有多少个，在经过若干次“把第一个字符扔到最后面”的操作之后变成回文串。 N,K<=10^9

Analysis

对于每个回文串考虑由它产生的不同字符串个数。 可以发现是跟它的最小周期d相关的。因为操作了d次之后又变回了原串，就重复了。 对于d为奇数的情况，字符串的贡献就是d 但是对于d为偶数的情况，贡献是d/2，因为回文串的周期串也必定回文，假设周期串S形如AA，显然把第一个A放到后面时就产生了重复。 奇数就是d的理由是周期串必定形如AcA，可以发现并不会重复。

那么问题变成求出“长度为N，字符集大小为K，最小周期长度为x”的字符串个数。递推去重即可。