← 返回题目列表

AtCoder · abc189_d

D. 逻辑表达式

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给出的是 N 字符串 S_1,\ldots,S_N,其中每个是 AND or OR.

查找 的元组数 N+1 变量 (x_0,\ldots,x_N),其中每个元素是 \text{True} or \text{False},这样以下计算结果为 y_N 正在 \text{True}:

  • y_0=x_0;
  • 为 i\geq 1, y_i=y_{i-1} \land x_i if S_i is AND,和 y_i=y_{i-1} \lor x_i if S_i is OR.

在这里, a \land b 和 a \lor b 是逻辑运算符。

约束

  • 1 \leq N \leq 60
  • S_i is AND or OR.

输入

输入由标准输入按以下格式给出:

N
S_1
\vdots
S_N

输出

打印答案。


示例输入 1

2
AND
OR

示例输出 1

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}

所有五个元组 (x_0,x_1,x_2) 导致 y_2 = \text{True} 如下所示:

  • (\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})

示例输入 2

5
OR
OR
OR
OR
OR

示例输出 2

63

除完全填充的元组之外的所有元组 \text{False} 结果 y_5 = \text{True}.