AT_abc189_d [ABC189D] 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$ 与 $b$ 的逻辑与，$a \lor b$ 表示 $a$ 与 $b$ 的逻辑或。

输入格式

输入以如下格式从标准输入读入：

$N$
$S_1$
$\vdots$
$S_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2
AND
OR

输出 #1

5

输入输出样例 #2

输入 #2

5
OR
OR
OR
OR
OR

输出 #2

63

说明/提示

限制条件

• $1 \leq N \leq 60$
• $S_i$ 为 AND 或 OR

样例解释 1

例如，当 $(x_0,x_1,x_2)=(\text{True},\text{False},\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}$。

使 $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$ 种。

样例解释 2

除了所有变量均为 $\text{False}$ 的情况外，其余 $2^6-1$ 种组合都能使 $y_5$ 为 $\text{True}$。

由 ChatGPT 4.1 翻译