WolfDelaymasterHard

作者：袁宇韬

关键词：动态规划

题目简述

给定一个由wo?三种字符组成的字符串$s$，问有多少种方案将?变为w或o，使得新字符串为若干个长度为偶数且前一半全部为w，后一半全部为o的字符串连接形成。答案对$10^9+7$取模。

算法一

将最终字符串中的每一段字符串的前一半称为w部分，后一半称为o部分。

用$f_i$表示前$i$个字符的答案。则容易通过枚举最后一段的长度得到一个$O(n^2)$的DP。考虑对这个DP的优化。

考虑$f_j$能够转移到$f_i$的条件。令$l = \frac{i - j}{2}$。分两种情况考虑。

如果w部分中只有?，则对于一个固定的$j$，w部分可行的条件为s[j..j+l-1]全部为?，o部分可行的条件为s[j..j+2*l-1]中没有w。满足条件的l为一个区间，可以用前缀和转移。

如果w部分中有至少一个w，则对于一个固定的$i$，w部分可行的条件为s[i-2*l..i-l-1]中没有o且有至少一个w，o部分可行的条件为s[i-l..i-1]中没有w。由于o部分中没有w，则w部分中一定包含s[i]之前的最近一个w字符，而o部分中则包含这个w字符之后的所有o字符。满足条件的l为一个区间，可以用前缀和转移。

时间复杂度$O(n)$。