Logical Expression

题目描述

给定 $N$ 个字符串 $S_1,\ldots,S_N$，每个字符串为 $AND$ 或 $OR$。 求有多少个长度为 $N+1$ 的元组 $(x_0,\ldots,x_N)$，其中每个元素为 $\text{True}$ 或 $\text{False}$，使得以下计算得到 $y_N$ 为 $\text{True}$：

$y_0=x_0$； 对于 $i\geq 1$，若 $S_i$ 为 $AND$，则 $y_i=y_{i-1} \land x_i$，若 $S_i$ 为 $OR$，则 $y_i=y_{i-1} \lor x_i$。

这里，$a \land b$ 和 $a \lor b$ 是逻辑运算符。

输入格式

输入从标准输入给出，格式如下： $N$ $S_1$ $\vdots$ $S_N$

输出格式

输出答案。

2
AND
OR

5

5
OR
OR
OR
OR
OR

63

提示

$1 \leq N \leq 60$ $S_i$ 为 $AND$ 或 $OR$。例如，如果 $(x_0,x_1,x_2)=(\text{True},\text{False},\text{True})$，我们有 $y_2 = \text{True}$，如下所示：

$y_0=x_0=\text{True}$ $y_1=y_0 \land x_1 = \text{True} \land \text{False}=\text{False}$ $y_2=y_1 \lor x_2 = \text{False} \lor \text{True}=\text{True}$

下面列出了所有 令 $y_2 = \text{True}$ 的五个元组 $(x_0,x_1,x_2)$：

$(\text{True},\text{True},\text{True})$ $(\text{True},\text{True},\text{False})$ $(\text{True},\text{False},\text{True})$ $(\text{False},\text{True},\text{True})$ $(\text{False},\text{False},\text{True})$
除全部为 $\text{False}$ 的那个元组外，所有元组都使得 $y_5 = \text{True}$。

标签: AtCoder|abc189D

来源

AtCoder|abc189D