【BZOJ3160】万径人踪灭

不会FFT也不会Manacher的蒟蒻来膜题

题意:给定一个01串,要求位置对称且不连续的回文子序列个数

首先可以想到的是用所有回文子序列减去回文子串

回文子串个数用Manacher求 以前一直搞不懂 现在想了想貌似挺simple的

求回文子序列只要求出按每个位置对称的数的对数即可

显然两个数加起来就等于他们对称轴的两倍

所以把这个串平方后即可得到关于每个位置对称的\(1\)的个数

取反后再做一次就可以得到\(0\)的

剩下的就很naive了

说点什么

您将是第一位评论人!

提醒
wpDiscuz