CF794G Replace All

Igor the analyst is at work. He learned about a feature in his text editor called "Replace All". Igor is too bored at work and thus he came up with the following problem: Given two strings $ x $ and $ y $ which consist of the English letters 'A' and 'B' only, a pair of strings $ (s,t) $ is called good if: - $ s $ and $ t $ consist of the characters '0' and '1' only. - $ 1

N/A

N/A

For the first sample, there are four possible pairs of $ (c',d') $ . If $ (c',d')=( $ AA $ , $ A $ ) $ , then the flexibility is $ 0 $ . If $ (c',d')=( $ AB $ , $ A $ ) $ , then the flexibility is $ 0 $ . If $ (c',d')=( $ AA $ , $ B $ ) $ , then the flexibility is $ 2 $ , as the pairs of binary strings $ ( $ 1 $ , $ 11 $ ) $ , $ ( $ 0 $ , $ 00 $ ) $ are the only good pairs. If $ (c',d')=( $ AB $ , $ B $ ) $ , then the flexibility is $ 0 $ . Thus, the total flexibility is $ 2 $ . For the second sample, there are $ 2^{1}+2^{2}+...+2^{10}=2046 $ possible binary strings of length not greater $ 10 $ , and the set of pairs of good strings is precisely the set of pairs $ (s,s) $ , where $ s $ is a binary string of length not greater than $ 10 $ .