@[AC_love](/user/186472) 三个回文字符串？
by hdkk @ 2024-04-04 18:45:55
@[AC_love](/user/186472) 三个非空字符串指的是三个非空回文字符串吗？
by cinout001_Wii @ 2024-04-04 18:46:26
我猜你说的是非空回文串，大力做一手：容易求出所有前缀回文和后缀回文，以及每个点为回文中心的区间，然后卷积。
by N_z_ @ 2024-04-04 18:49:59
我不知道容不容易卷积，但是 $n^2/w$ 直接 bitset 是容易完成的。
by N_z_ @ 2024-04-04 18:51:01
标记一下回文前后缀，枚举每个位置随便求一下回文半径，然后看看两边对折一下能不能有标记的位置对上，好像就好了。
by fangzichang @ 2024-04-04 18:51:07
哦哦想一块去了。
by fangzichang @ 2024-04-04 18:51:27
@[hdkk](/user/728778) @[cinout001_Wii](/user/138492) 还真是，打错了，不好意思
by AC_love @ 2024-04-04 19:33:15
@[N_z_](/user/320087) 感觉好对，拜谢大佬
by AC_love @ 2024-04-04 19:33:28
@[fangzichang](/user/678087) %%%
by AC_love @ 2024-04-04 19:34:08
这个做法要用回文树。
类似 CF932G 这个题，那个题要做的是求偶回文划分，你这个题没有限制偶回文，不过应该差不多？
假设你要分成 $k$ 段，就做 $k$ 轮 dp，每次 $n \log n$。
那复杂度就是 $O(k n\log n)$，你这里的 $k$ 是 3。
也可以位运算优化，因为你只关注合法性，就可以把 $k$ 除以 $w$ 。
by xkai @ 2024-04-04 20:43:00