D - Logical Expression Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N 個の文字列 S_1,\ldots,S_N が与えられます。各文字列は AND または OR です。

値が \text{True} または \text{False} であるような N+1 個の変数の組 (x_0,\ldots,x_N) であって、 以下のような計算を行った際に、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 の論理和を表します。

制約

  • 1 \leq N \leq 60
  • S_i は AND または 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_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

5
OR
OR
OR
OR
OR

出力例 2

63

全てが \text{False} のときを除く 2^6-1 通りで y_5 は \text{True} になります。

Score : 400 points

Problem Statement

Given are N strings S_1,\ldots,S_N, each of which is AND or OR.

Find the number of tuples of N+1 variables (x_0,\ldots,x_N), where each element is \text{True} or \text{False}, such that the following computation results in y_N being \text{True}:

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

Here, a \land b and a \lor b are logical operators.

Constraints

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

Input

Input is given from Standard Input in the following format:

N
S_1
\vdots
S_N

Output

Print the answer.

Sample Input 1

2
AND
OR

Sample Output 1

5

For example, if (x_0,x_1,x_2)=(\text{True},\text{False},\text{True}), we have y_2 = \text{True}, as follows:

  • 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}

All of the five tuples (x_0,x_1,x_2) resulting in y_2 = \text{True} are shown below:

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

Sample Input 2

5
OR
OR
OR
OR
OR

Sample Output 2

63

All tuples except the one filled entirely with \text{False} result in y_5 = \text{True}.