Skills101
← All coding problems

Boolean Parenthesization

mediumDynamic Programming II+20 XPTime limit 3s

An expression alternates the values T (true) and F (false) with the operators & (AND), | (OR) and ^ (XOR), for example T|F&T^F. Count the number of ways to fully parenthesise it so that it evaluates to true. Print the count modulo 1 000 000 007.

Input: one line with the expression (no spaces).

Output: the number of ways modulo 10⁹ + 7.

Constraints: the expression has n values and n − 1 operators, 1 ≤ n ≤ 150.

Example: T^F&T has two bracketings: (T^F)&T is true and T^(F&T) is true, so the answer is 2.

Think about it: interval DP counting both outcomes: T[i][j] and F[i][j] = ways for values i … j to become true / false. Split at every operator k between them and combine: for &, true needs both sides true; for |, true unless both are false; for ^, true when the sides differ. O(n³).

Sample input 1

T^F&T

Sample output 1

2

Sample input 2

T|F&T^F

Sample output 2

5

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.