実行時間制限: 2 sec / メモリ制限: 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 isOR
.
Here, a \land b and a \lor b are logical operators.
Constraints
- 1 \leq N \leq 60
- S_i is
AND
orOR
.
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}.