题目链接
太深刻了。
循环移位的特征在于，其是一个一对一的映射，就必然形成若干环状。我们求解可达的点数量，可以让每个点只被距离其最近的特殊点计算。也即，计算每个特殊点到下一个特殊点的距离并求和。
如果一个字符串循环移位 \(t\) 次后等于自己，那么其必然有长为 \(t\) 的约数的整周期。
证明：由条件可得该字符串具有长为 \(t\) 和 \(n-t\) 的周期，由强周期引理可知其有长为 \(\gcd(t,n-t)=\gcd(t,n)\) 的周期。由于是 \(n\) 的因数故其为整周期。
因此，对于一个串，考虑找到其最小整周期 \(s\)，则其到下一特殊点步数 \(t\) 满足 \(t\le s\)，且其循环移位 \(0\sim s-1\) 步形成的字符串都互不相同。
将原串 \(A\) 循环移位 \(t\) 次完全等价于将 \(A\) 的整周期循环移位 \(t\) 次。
对于回文串来说，由 border 的性质可知，其所有整周期也都是回文串。由于我们要求移位之后还是回文，考虑原来整周期 \(T\) 是 \(X(长为s-t)+Y(长为t)\)，移位后是 \(Y+X\)，要求 \(Y+X=反X+反Y\)。因为 \(T\) 是回文串，所以 \(T=反Y+反X\)。则将 \(T\) 循环移位 \(s-t\) 次可以得到 \(反X+反Y\)。
上面的步骤总结一下就是 \(T\) 循环移位 \(t\) 次和循环移位 \(s-t\) 次相等的时候就到了下一个回文处。由于循环移位 \(0\sim s-1\) 步互不相同，所以必然只有 \(t=s-t\) 和 \(t=s\) 两个解了。
那么结论就是，假设最小整周期长度为 \(s\)，若 \(s\) 为偶数则贡献为 \(\frac{s}{2}\)，否则贡献为 \(s\)。
现在情况就清楚了，我们枚举最小整周期长度 \(s\)，容斥计算最小整周期恰好是 \(s\) 的回文串数量，然后直接乘奇偶性对应的贡献系数即可。时间复杂度 \(O(d^2(n))\)