ABC189 D Logical Expression
DPをする. $ dp_{i,j} := $ y_iまで決めて, $ x_iを$ jにするときの場合の数 とする.
初期化は$ dp_{0, 0} = dp_{0, 1} = 1とすればよい.
遷移は次のようになる.
・$ dp_{i + 1, 1} = dp_{i + 1, 1} + dp_{i, 1}, $ dp_{i + 1, 0} = dp_{i + 1, 0} + dp_{i, 1} + dp_{i, 0} * 2 ($ S_i = "AND"のとき)
・$ dp_{i + 1, 1} = dp_{i + 1, 1} + dp_{i, 1} * 2 + dp_{i, 0}, $ dp_{i + 1, 0} = dp_{i + 1, 0} + dp_{i, 0} ($ S_i = "OR"のとき)
計算量は$ O(N)となる.