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

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdbool.h>

#define MOD 1000000007
typedef unsigned long long ull;

bool isValid(char *exp, int len) {
    if (len % 2 == 0) {
        return false;
    }
    for (int i = 0; i < len; i += 2) {
        if (exp[i] != '0' && exp[i] != '1') {
            return false;
        }
    }
    for (int i = 1; i < len; i += 2) {
        if (exp[i] != '&' && exp[i] != '|' && exp[i] != '^') {
            return false;
        }
    }
    return true;
}

int main(void) {
    char exp[501], desStr[6];
    int len;
    bool des;
    scanf("%s%s", exp, desStr);
    len = strlen(exp);
    des = strcmp(desStr, "true") == 0;
    if (!isValid(exp, len)) {
        printf("0\n");
        return 0;
    }

    ull **t, **f;
    t = (ull **) malloc(sizeof(ull *) * len);
    f = (ull **) malloc(sizeof(ull *) * len);
    for (int i = 0; i < len; i++) {
        t[i] = (ull *) calloc(len, sizeof(ull));
        f[i] = (ull *) calloc(len, sizeof(ull));
    }
    t[0][0] = exp[0] == '1' ? 1 : 0;
    f[0][0] = exp[0] == '0' ? 1 : 0;
    for (int i = 2; i < len; i += 2) {
        t[i][i] = exp[i] == '1' ? 1 : 0;
        f[i][i] = exp[i] == '0' ? 1 : 0;
        for (int j = i - 2; j >= 0; j -= 2) {
            for (int k = j; k < i; k += 2) {
                if (exp[k + 1] == '&') {
                    t[j][i] = (t[j][i] + (t[j][k] * t[k + 2][i]) % MOD) % MOD;
                    f[j][i] = (f[j][i] + (t[j][k] * f[k + 2][i]) % MOD) % MOD;
                    f[j][i] = (f[j][i] + (f[j][k] * t[k + 2][i]) % MOD) % MOD;
                    f[j][i] = (f[j][i] + (f[j][k] * f[k + 2][i]) % MOD) % MOD;
                } else if (exp[k + 1] == '|') {
                    t[j][i] = (t[j][i] + (t[j][k] * f[k + 2][i]) % MOD) % MOD;
                    t[j][i] = (t[j][i] + (f[j][k] * t[k + 2][i]) % MOD) % MOD;
                    t[j][i] = (t[j][i] + (t[j][k] * t[k + 2][i]) % MOD) % MOD;
                    f[j][i] = (f[j][i] + (f[j][k] * f[k + 2][i]) % MOD) % MOD;
                } else {
                    t[j][i] = (t[j][i] + (t[j][k] * f[k + 2][i]) % MOD) % MOD;
                    t[j][i] = (t[j][i] + (f[j][k] * t[k + 2][i]) % MOD) % MOD;
                    f[j][i] = (f[j][i] + (t[j][k] * t[k + 2][i]) % MOD) % MOD;
                    f[j][i] = (f[j][i] + (f[j][k] * f[k + 2][i]) % MOD) % MOD;
                }
            }
        }
    }

    printf("%llu\n", des ? t[0][len - 1] : f[0][len - 1]);
    return 0;
}