CF582E Boolean Function 题解

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;
}