CF1930I Counting Is Fun

You are given a binary $ ^\dagger $ pattern $ p $ of length $ n $ . A binary string $ q $ of the same length $ n $ is called good if for every $ i $ ( $ 1 \leq i \leq n $ ), there exist indices $ l $ and $ r $ such that: - $ 1 \leq l \leq i \leq r \leq n $ , and - $ p_i $ is a mode $ ^\ddagger $ of the string $ q_lq_{l+1}\ldots q_r $ . Count the number of good binary strings modulo $ 998\,244\,353 $ . $ ^\dagger $ A binary string is a string that only consists of characters $ \mathtt{0} $ and $ \mathtt{1} $ . $ ^\ddagger $ Character $ c $ is a mode of string $ t $ of length $ m $ if the number of occurrences of $ c $ in $ t $ is at least $ \lceil \frac{m}{2} \rceil $ . For example, $ \mathtt{0} $ is a mode of $ \mathtt{010} $ , $ \mathtt{1} $ is not a mode of $ \mathtt{010} $ , and both $ \mathtt{0} $ and $ \mathtt{1} $ are modes of $ \mathtt{011010} $ .

N/A

N/A

In the second example, the good strings are - $ \mathtt{010} $ ; - $ \mathtt{011} $ ; - $ \mathtt{101} $ ; - $ \mathtt{110} $ ; - $ \mathtt{111} $ .