https://practice.geeksforgeeks.org/problems/boolean-parenthesization/0

Given a boolean expression with following symbols.

Symbols
‘T’ —> true
‘F’ —> false

And following operators filled between symbols

Operators
& —> boolean AND
| —> boolean OR
^ —> boolean XOR

Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.

For Example:
The expression is “T | T & F ^ T”, it evaluates true
in 4 ways ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T)
and (T|((T&F)^T)).

dp[ i ][ j ][ 0/1 ] 表示字符 i - j 区间内取 true 的个数和取 false 的个数。状态转移： dp[ i ][ j ][ ? ] += dp[ i ][ h ][ ? ] * dp[ h+1 ][ j ][ ? ], 其中 “ ？”根据具体情况而定。
按照字符长度由下向上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sf(n) scanf("%d",&n)
#define sfs(n) scanf("%s",n);
#define pf(n) printf("%d",n)
#define pfc(c) printf(c)
#define fi(i,s,t) for(int i=s;i<t;i++)
#define fd(s,t) for(int i=s-1;i>=t;i--)
#define mem(a,c) memset(a,c,sizeof(a))
const int MAX=100+5;
const int MOD=1003;
int t,n,ans,dp[MAX][MAX][2],xl,yl;
char x[MAX],y[MAX],a[MAX],tmp;
void f(){
	mem(dp,0);
	fi(i,0,xl)
		if(x[i]=='T') {
			dp[i][i][0]=1;dp[i][i][1]=0;
		}
		else {
			dp[i][i][0]=0;dp[i][i][1]=1;
		}
	fi(k,1,xl)
		fi(i,0,xl-k ){
			int j=i+k;
			fi(h,i,j){
				int t1,t2,t3,t4;
				t1=dp[i][h][0] * dp[h+1][j][0];
				t2=dp[i][h][0] * dp[h+1][j][1];
				t3=dp[i][h][1] * dp[h+1][j][0];
				t4=dp[i][h][1] * dp[h+1][j][1];
				switch(y[h]){
					case '|': 
						dp[i][j][0] += t1 + t2 + t3;
						dp[i][j][1] += t4;break;
					case '&':
						dp[i][j][0] += t1;
						dp[i][j][1] += t2 + t3 + t4; break;
					case '^': 
					    dp[i][j][0] += t2 + t3;
						dp[i][j][1] += t1 + t4; break;
				}
				dp[i][j][0]%=MOD;dp[i][j][1]%=MOD;
			}
		}
}
int main(){
	freopen("in","r",stdin);
	sf(t);
	while(t--){
		ans = 0;
		xl=0,yl=0;
		sf(n);
		sfs(a);
		fi(i,0,n){
			tmp=a[i];
			if(tmp=='T' || tmp=='F') x[xl++] = tmp;
			else if(tmp=='|' || tmp=='&' || tmp=='^') y[yl++] = tmp;
		}
		f();
		pf(dp[0][xl-1][0]);pfc("\n");
	}
	return 0;
}