标签：复杂度 位置 然后 ShiftTable sqrt 考虑

[ABC304F] Shift Table

考虑直接枚举所有可能的 \(m\) 计算答案。对于串中是 # 的位置是自由的，. 的位置则是锁定的。考虑对于一个 \(m\)，如果原串中 \(s_i=\) .，那么由于新串是由前 \(m\) 个字符构造而成的，那么必须满足 \(S_{(i-1)\mod m+1}=\) # 。然后自由的位置假设有 \(w\) 个，贡献就有 \(2^{w}\)。这样做的话复杂度是 \(O(n\sqrt n)\)。然后再考虑这样做的话会有重复。但是我们由于一个 \(x\) 的答案，一定对于它的倍数 \(y\) 来说都是合法的，那么我们只需在计算 \(y\) 时去掉贡献。然后这样复杂度就是 \(O(\sqrt n \sqrt i)\)。总复杂度就是 \(O(n\sqrt n)\)。

code

标签：复杂度,位置,然后,ShiftTable,sqrt,考虑
From： https://www.cnblogs.com/wscqwq/p/17470748.html