link

0x00 思路

先看题。
「Zxl 决定制造一条项链，她买了一串珠子，她有一个机器，能把这条珠子切成很多段，使得每段恰有 \(k\) 个珠子 ，如果这条珠子的长度不是 \(k\) 的倍数，最后一块长度小于 \(k\) 的段就被丢弃了。」

「Zxl 想知道，选择什么数字 \(k\) 可以得到最多的不同的段。注意这里的段是可以反转的，即，子串 \(1,2,3\) 和 \(3,2,1\) 被认为是一样的。」

题面真长，简化一下再看。

由于我们希望可以辨别出不同的顺序，所以我们需要使用字符串哈希来做题（若没有哈希冲突那么每一种不同的顺序哈希值都不同）。但是如果是可以反转的话，那么我们就需要将整个字符串反转后的哈希值同样进行计算和存储。

code

#include

建议再做 SP15569 或继续阅读 。