bzoj 3160: 万径人踪灭 — FFT,manacher

  • 2018-01-18
  • 0
  • 0

 

3160: 万径人踪灭

Time Limit: 10 Sec  Memory Limit: 256 MB

Description

 

Source

不难发现,ans=总方案 – 连续子串

考虑总方案,枚举对称轴,方案数就是2^f(i) -1,f(i) 表示有多少对关于对称轴对称

那么如何求f(i),

很容易发现式子就是FFT卷积,那就把a,b拆开分别求一遍FFT就好了

连续的就直接manacher咯

 

评论

还没有任何评论,你来说两句吧