题解 | 表达式得到期望结果的组合种数

package main

import (
	"fmt"
)

func main() {
	var str string
	var desired bool
	for {
		n, _ := fmt.Scan(&str, &desired)
		if n == 0 {
			break
		} else {
			if isValid(str) {
				fmt.Println(process(str, desired))
			} else {
				fmt.Println(0)
			}
		}
	}
}
func isValid(str string) bool {
	if len(str)&1 == 0 {
		return false
	}
	for i := 0; i < len(str); i += 2 {
		if !(str[i] == '0' || str[i] == '1') {
			return false
		}
	}

	for i := 1; i < len(str); i += 2 {
		if !(str[i] == '&' || str[i] == '|' || str[i] == '^') {
			return false
		}
	}
	return true
}
func process(str string, desired bool) int {
	// base case 所在位置，不可能压中逻辑符号, 只能为0，1
	truedp := make([][]int, len(str))
	falsedp := make([][]int, len(str))
	n := len(str)
	for i := 0; i < n; i++ {
		truedp[i] = make([]int, n)
		falsedp[i] = make([]int, n)
	}

	for i := 0; i < n; i += 2 {
		if str[i] == '1' {
			truedp[i][i] = 1
		} else {
			falsedp[i][i] = 1
		}
	}
    mod := int(1e9+7)
	for row := n - 3; row >= 0; row = row - 2 {
		for col := row + 2; col < n; col = col + 2 {
			for i := row + 1; i < col; i += 2 {
				if str[i] == '&' {
					truedp[row][col] += (truedp[row][i-1] * truedp[i+1][col])%mod
				} else if str[i] == '|' {
					truedp[row][col] += (truedp[row][i-1] * truedp[i+1][col])%mod
					truedp[row][col] += (truedp[row][i-1] * falsedp[i+1][col])%mod
					truedp[row][col] += (falsedp[row][i-1] * truedp[i+1][col])%mod
				} else if str[i] == '^' {
					truedp[row][col] += (truedp[row][i-1] * falsedp[i+1][col])%mod
					truedp[row][col] += (falsedp[row][i-1] * truedp[i+1][col])%mod
				}
                truedp[row][col] = (truedp[row][col])%mod

				if str[i] == '&' {
					falsedp[row][col] += (truedp[row][i-1] * falsedp[i+1][col])%mod
					falsedp[row][col] += (falsedp[row][i-1] * truedp[i+1][col])%mod
					falsedp[row][col] += (falsedp[row][i-1] * falsedp[i+1][col])%mod
				} else if str[i] == '|' {
					falsedp[row][col] += (falsedp[row][i-1] * falsedp[i+1][col])%mod
				} else if str[i] == '^' {
					falsedp[row][col] += (truedp[row][i-1] * truedp[i+1][col])%mod
					falsedp[row][col] += (falsedp[row][i-1] * falsedp[i+1][col])%mod
				}

                falsedp[row][col] = (falsedp[row][col])%mod
			}
		}
	}

	if desired {
		return truedp[0][n-1]
	} else {
		return falsedp[0][n-1]
	}

}

// 1^0|0|1
// func process(str string, desired bool, l, r int) int {
// 	// base case 所在位置，不可能压中逻辑符号, 只能为0，1
// 	if l == r {
// 		if str[l] == '1' {
// 			if desired {
// 				return 1
// 			}
// 			return 0
// 		} else {
// 			if desired {
// 				return 0
// 			}
// 			return 1
// 		}
// 	}

// 	ans := 0
// 	if desired {
// 		for i := l + 1; i < r; i += 2 {
// 			if str[i] == '&' {
// 				ans += process(str, true, l, i-1) * process(str, true, i+1, r)
// 			} else if str[i] == '|' {
// 				ans += process(str, true, l, i-1) * process(str, true, i+1, r)
// 				ans += process(str, true, l, i-1) * process(str, false, i+1, r)
// 				ans += process(str, false, l, i-1) * process(str, true, i+1, r)
// 			} else if str[i] == '^' {
// 				ans += process(str, true, l, i-1) * process(str, false, i+1, r)
// 				ans += process(str, false, l, i-1) * process(str, true, i+1, r)
// 			}
// 		}
// 	} else {
// 		for i := l + 1; i < r; i += 2 {
// 			if str[i] == '&' {
// 				ans += process(str, true, l, i-1) * process(str, false, i+1, r)
// 				ans += process(str, false, l, i-1) * process(str, true, i+1, r)
// 				ans += process(str, false, l, i-1) * process(str, false, i+1, r)
// 			} else if str[i] == '|' {
// 				ans += process(str, false, l, i-1) * process(str, false, i+1, r)
// 			} else if str[i] == '^' {
// 				ans += process(str, true, l, i-1) * process(str, true, i+1, r)
// 				ans += process(str, false, l, i-1) * process(str, false, i+1, r)
// 			}
// 		}
// 	}
// 	return ans
// }