D. Om Nom and Necklace
题意：给定一个n长的字符串和一个k。询问每个前缀是不是ABABABA这样的形式，其中B有k个，A有k+1个，AB都可以为空。
思路：先说结论吧，既然AB都可以为空，那把AB看成一个串C那就是CCCC..A，A又是C的前缀，这显然是循环节，所以对于一个前缀，如果它存在这么一个循环节，其周期刚好是k，就是合法的。另外还有一种特殊情况，就是B为空，也就是A=C，那么就是刚好由K+1个一样的字符串组成也合法。那么怎么实现呢，我们知道循环节是根据kmp的border函数得来的，但对于一个前缀只有一个border，而这个border算出来的循环节不一定符合条件，然而border的border实际上也是可以算出他的循环节的，所以思路很明确了，构造border树，对每一个前缀，如果合法，其循环节肯定是它祖先某个节点得来，而border树上一条链的下标必然是递增，所以有一个单调关系，所以我每次找到这个前缀对应的点，然后对其祖先这条链做倍增，复杂度按理说是o(nlongn)的，但我也不知道为什么要跑九百多ms。