CF582E - Boolean Function
$ made by Ameiyo $
首先将表达式转换成表达式树。
令 $ f[u][s] $ 表示 $ u $ 这棵子树中，在 $ n $ 组取值的情况下， $ n $ 组结果为 $ s $ 的方案数。
首先每一位的转移是互不影响的，因为只是把他们放到一起而已，所以 $ s1, s2 $ 与 符号 $ opr $ 所转移到的地方就是 $ s1 opr s2 $ 。
所以可以先写出一个暴力算法。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define reg register
#define rep(i, a, b) for (reg int i = (a), i##end = (b); i <= i##end; ++i)
#define dep(i, a, b) for (reg int i = (a), i##end = (b); i >= i##end; --i)
template <typename _typer> inline _typer read() {
_typer init = 0;
char ch = getchar(), k = 0;
for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-');
for ( ; isdigit(ch); ch = getchar())
init = (init << 3) + (init << 1) + (ch ^ 48);
return k ? -init : init;
}
const ll N = 505, INF = 1e9;
const ll M = (1 << 16), Mod = 1e9 + 7;
/*******************************************************************************
*
*
*
******************************************************************************/
int n, tot;
int lson[N], rson[N], node[N], f[N][M], ChTpInt[N], cnt[N];
string s;
struct NODE { int id, rt; } ;
NODE Change(int l, int r) {
int u = ++tot, id = l;
// cerr << l << " " << r << endl;
rep (i, l, r) {
id = i;
if (s[i] == '(') {
NODE tmp = Change(i + 1, r);
if (lson[u]) rson[u] = tmp.rt;
else lson[u] = tmp.rt;
id = i = tmp.id;
continue;
}
// cerr << s[i] << endl;
if (s[i] == ')') break;
if (s[i] != '?') {
node[u] = s[i];
} else if (s[i + 1] == '(') { // opr - ?
node[u] = 1;
} else { // num - ?
node[u] = 2;
}
}
// cerr << u << " " << node[u] << " " << id << endl;
// system("pause");
return (NODE) { id, u };
}
int val[N][10], ans[N];
int Get(int x, int y, int ch) {
if (ch == '|') return x | y;
else if (ch == '&') return x & y;
return 0;
}
void Upd(int &x, int y) { ((x += y) >= Mod && (x -= Mod)); }
void Dfs(int u) {
// cerr << u << " " << ((node[u] == 1 || node[u] == 2) ? node[u] : (char) node[u]) << endl;
if (!u) return ;
if (node[u] == 2) {
rep (i, 1, 8) {
int w = 0;
rep (j, 1, n) if (val[j][i]) w |= (1 << j >> 1);
cnt[u] += (!f[u][w]), ++f[u][w];
}
} else if (isalpha(node[u])) {
int w = 0;
rep (j, 1, n) if (val[j][ChTpInt[node[u]]]) w |= (1 << j >> 1);
cnt[u] += (!f[u][w]), ++f[u][w];
} else {
int ls = lson[u], rs = rson[u];
Dfs(ls), Dfs(rs);
if (cnt[ls] > cnt[rs]) swap(ls, rs);
rep (s1, 0, (1 << n) - 1) if (f[ls][s1]) {
rep (s2, 0, (1 << n) - 1) if (f[rs][s2]) {
int tmp = 1ll * f[ls][s1] * f[rs][s2] % Mod;
if (node[u] == 1) {
Upd(f[u][Get(s1, s2, '|')], tmp);
Upd(f[u][Get(s1, s2, '&')], tmp);
} else Upd(f[u][Get(s1, s2, node[u])], tmp);
}
}
}
}
int main() {
cin >> s;
n = read<int>();
rep (i, 0, 3) ChTpInt['A' + i] = i + 1, ChTpInt['a' + i] = i + 5;
int w = 0;
rep (i, 1, n) {
rep (d, 1, 4) val[i][d + 4] = (val[i][d] = read<int>()) ^ 1;
if (read<int>()) w |= (1 << i >> 1);
}
NODE tmp = Change(0, s.length() - 1);
// cerr << "Change end" << endl;
Dfs(tmp.rt);
printf("%d\n", f[tmp.rt][w]);
return 0;
}
但是这会血 T ，所以要对整个方案进行改进。
先只考虑 & 。
我们要统计的是满足 $ s = s1 & s2 $ 的 $ f[ls][s1] * f[rs][s2] $ 的和，因为 $ s = s1 & s2 $ ，所以 $ s $ 肯定是 $ s1 , s2 $ 最大公共子集。
令 $ sum[s] $ 表示所有包含 $ s $ 的状态的和， $ tmp[s] $ 表示 & 之后状态为 $ s $ 的总和。
那么 $ tmp[s] = sum[ls][s] * sum[rs][s] - \sum tmp[s'] $ ，其中 $ s \subset s' $ 。
为什么要减去包含 $ s $ 的值？因为包含 $ s $ 的两个数可能还有其他公共部分，那么他们 & 之后的结果就是 $ s' $ 了。
关于 $ sum $ 数组我们可以用 高维前(后)缀和 简单的解决掉，但是该如何容斥出 $ tmp $ 数组呢？
我直接类似高维前缀和弄了个高维前缀减，尽管并不知道为什么能这么用， 。
考虑两个状态 $ s, s' $ ，其中 $ s \subset s' $ ，设从 $ s $ 到 $ s' $ 需要 $ t $ 步。
因为我们把高维前缀和中的 + 变成了 - ，所以因为负负得正， $ s $ 对 $ s' $ 做的贡献就是 $ (-1) ^ t $ 。
$ sum[ls][s] * sum[rs][s] $ 的到的结果是包含所有 $ tmp[s'] (s \in s') $ 的，所以一开始的值都包含了所有的 "孩子" (在上面的博客中我将包含与不包含定义成了 父子关系)。
对于所有 $ s'' $ 满足 二进制位中 只有 那 $ t $ 位上与 $ s $ 有 $ i $ 位不同(即那 $ i $ 位值为 $ 1 $ ，其他几位和 $ s $ 一模一样) ，会对 $ s' $ 贡献 $ s $ ， 而每个的贡献是 $ (-1) ^ {t - i} $ ，对于每个 $ i $ 一共有 $ C_{t} ^{i} $ 个这样的数，所以 $ s $ 在 $ s' $ 的系数就是 $ \sum _{i = 0} ^{t} (C_{t} ^{i} * (-1) ^{t - i}) $ (在更新之前系数是 $ 1 $ )。
那个时候还根本不会算这个东西，今天打题解的时候突然想到了前两天刚看的多项式定理，当然这里只用到了 二项式定理。
二项式定理:
那么当 $ x = 1, c = -1 $ 时，右边就是上面的式子，而值 $ (1 - 1) ^ t = 0 $ ，即最后在 $ tmp[s'] $ 中不包含 $ tmp[s] $ 。
即证。
还要考虑 | 运算。其实或运算就是 补集做了与运算后再取补集，即 $ C _U (s1 | s2) = C _U s1 & C _U s2 $ 。
所以转换成 & 就行了。
void Dfs(int u) {
if (!u) return ;
memset(f, 0, sizeof f);
if (node[u] == 2) {
rep (i, 1, 8) {
int w = 0;
rep (j, 1, n) if (val[j][i]) w |= (1 << j >> 1);
++f[w];
}
} else if (isalpha(node[u])) {
int w = 0;
rep (j, 1, n) if (val[j][ChTpInt[node[u]]]) w |= (1 << j >> 1);
++f[w];
} else {
int ls = lson[u], rs = rson[u];
Dfs(ls), Dfs(rs);
dep (s, uplim, 0) {
tmpS[s] = 1ll * S[ls][s] * S[rs][s] % Mod;
tmpC[s] = 1ll * C[ls][s] * C[rs][s] % Mod;
}
rep (i, 0, n - 1) rep (s, 0, uplim)
if (!(s & (1 << i))) {
Upd(tmpS[s], Mod - tmpS[s | (1 << i)]);
Upd(tmpC[s], Mod - tmpC[s | (1 << i)]);
}
rep (s, 0, uplim) {
if (node[u] == 1) {
// |
f[s] = tmpC[uplim ^ s];
// &
Upd(f[s], tmpS[s]);
} else if (node[u] == '|') {
f[s] = tmpC[uplim ^ s];
} else if (node[u] == '&') {
f[s] = tmpS[s];
}
}
}
rep (s, 0, uplim) S[u][s] = C[u][uplim ^ s] = f[s];
rep (i, 0, n - 1) rep (s, 0, uplim)
if (!(s & (1 << i))) {
Upd(S[u][s], S[u][s | (1 << i)]);
Upd(C[u][s], C[u][s | (1 << i)]);
}
}
$ in 2019.9.27 $