Visits: 283

CF582E Boolean Function

题意

• A,B,C,D,a,b,c,d 为八个布尔「变量」，其中小写字母的值等于对应大写字母的值取反。
• &,| 为两个布尔「操作符」。
• 布尔「表达式」为一个「变量」，或通过「操作符」连接起来的两个「表达式」。
• 布尔「函数」f(A,B,C,D) 为一个布尔「表达式」。
• 给定一个可能缺少某些「变量」和「操作符」（用 ? 代替）的「函数」s，并给出 $n$ 个函数在 A,B,C,D 确定时的值。
• 求可能的「函数」个数。
• $|\texttt{s}|\le 500$，$n \le 16$，答案对 $10^9+7$ 取模。

题解

先建出表达式树，设 $f[i][j]$ 表示树中点 $i$ 处将 $n$ 个值压缩成 $j$ 的方案数。

对于一个非叶节点 $i$ 转移为
$$
f[i][x] = \sum_{x = y \oplus z} f[j][y] \times f[k][z]
$$
因此可以 FWT 优化，总时间复杂度 $\mathcal O(|\texttt{s}|n2^n)$。

代码

const int N = 507, M = 16;
int k, n, m, fa[N], t = 1, p = 1;
char s[N], c[N];
int h[M|1][5];
vi e[N];
modint f[N][1<<M|1], a[1<<M|1], b[1<<M|1];

inline void in(modint *A, modint *B) {
    for (int i = 0; i < n; i++) a[i] = A[i], b[i] = B[i];
}

inline void get() {
    for (int i = 0; i < n; i++) a[i] *= b[i];
}

inline void out(modint *f) {
    for (int i = 0; i < n; i++) f[i] += a[i];
}

inline void OR(modint *f, modint x = 1) {
    for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for (int i = 0; i < n; i += o)
            for (int j = 0; j < k; j++)
                f[i+j+k] += f[i+j] * x;
}

inline void AND(modint *f, modint x = 1) {
    for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for (int i = 0; i < n; i += o)
            for (int j = 0; j < k; j++)
                f[i+j] += f[i+j+k] * x;
}

void dfs(int x) {
    if (!e[x].size()) {
        if (c[x] == '?')
            for (int i = 0; i < 4; i++) {
                int k = 0;
                for (int j = 0; j < m; j++) k |= h[j][i] << j;
                f[x][k] += 1, f[x][((1<<m)-1)^k] += 1;
            }
        else {
            int i = c[x] - (c[x] >= 'A' && c[x] <= 'D' ? 'A' : 'a'), k = 0;
            for (int j = 0; j < m; j++) k |= h[j][i] << j;
            f[x][c[x]>='A'&&c[x]<='D'?k:(((1<<m)-1)^k)] += 1;
        }
        return;
    }
    dfs(e[x][0]);
    dfs(e[x][1]);
    if (c[x] != '&') in(f[e[x][0]], f[e[x][1]]), OR(a), OR(b), get(), OR(a, P - 1), out(f[x]);
    if (c[x] != '|') in(f[e[x][0]], f[e[x][1]]), AND(a), AND(b), get(), AND(a, P - 1), out(f[x]);
}

int main() {
    rds(s, k), rd(m), n = 1 << m;
    for (int i = 1; i <= k; i++)
        if (s[i] == '(') e[p].pb(++t), fa[t] = p, p = t;
        else if (s[i] == ')') p = fa[p];
        else c[p] = s[i];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < 5; j++)
            rd(h[i][j]);
    dfs(1);
    int o = 0;
    for (int i = 0; i < m; i++) o |= h[i][4] << i;
    print(f[1][o]);
    return 0;
}