5372: [Pkusc2018]神仙的游戏

这题务必用fft写,反正ntt我bzoj一直tle,loj 8s

做这题首先要知道一个性质,如果选取长度为len的串,那么该串可行,一定满足不存在一对 01,其距离相差len
(X而不是一开始我想的类似 另外一个fft的题...
那么如果存在一对01其距离差为len,那么对于所有k|len的串都不可行。
考虑首先求出所有01串的差值len, 暴力n^2肯定不行
考虑两个数组a,b,若s[i] = 0则 a[i] = 1,否则 b[i] = 1
那么对于两个位置 a[i] = 1, b[j] = 1,abs(j - i)就是一个不合法情况
考虑用fft怎么优化,容易知道令a[i] = a[i] * x^i b[i] = b[i] * x^i
那么 a[i] * b[j] = a[i] * b[j] * x^{i+j}
而想要的到的是 i-j,那么考虑把其中一个数组反转,即 j变为 n-j+1
那么此时转化为a[i] * b[n-j+1] = a[i] * b[j] * x^{i+n-j+1}
那么这个时候很显然fft能直接优化了,搞定
复杂度O(n\log n)

fft:

ntt:

 

4 + 1 =