D - 逻辑表达式

得分: $400$ 分

问题描述

给定 $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$ 是逻辑运算符。

约束

• $1 \leq N \leq 60$
• $S_i$ 是 AND 或 OR。

输入

从标准输入中以以下格式给出：

$N$

$S_1$

$\vdots$

$S_N$

输出

输出答案。

2
AND
OR

5

例如，如果 $(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})$

5
OR
OR
OR
OR
OR

63

除了填满了 $\text{False}$ 的元组之外，所有的元组都导致 $y_5 = \text{True}$。