拆位优化 DP
stripe_python · · 算法·理论
一个比较简单的 trick,用于优化转移与位运算有关的 DP。
下文记
P4310 绝世好题
定义序列
b_i 是优美的,当且仅当\forall 1 \le i<|b|, b_i \text { and } b_{i+1} \ne 0 。给定一个长为
n 的序列a_i ,求出最长优美子序列长度。
:::::success[题解]
我们有经典的
记
从而
转移顺序为先
复杂度
:::::
:::::info[代码]
int n, a[N], g[40];
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
int f = 0;
for (int j = 0; j <= 31; j++)
if (a[i] >> j & 1) chkmax(f, g[j]);
for (int j = 0; j <= 31; j++)
if (a[i] >> j & 1) chkmax(g[j], f + 1);
}
cout << *max_element(dp, dp + 32);
}
:::::
NC294483 Kingdom Path
给定长为
n 的序列a_i 。构造一张n 个点的有向图,对于节点i,j ,若i<j 则两点间连接\text{popcount}(a_i \text{ and } a_j) 条边。求从节点
1 到n 的简单路径数目,对10^9+7 取模。多测,
T \le 5 ,n \le 2 \times 10^5 ,a_i < 2^{30} ,2 秒,256 MB。
:::::success[题解]
记
考察上式的组合意义:每个
从而在转移到
复杂度
:::::
:::::info[代码]
const int N = 2e5 + 5;
int n, a[N];
mint f[N], g[35];
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
fill(f + 1, f + n + 1, 0), fill(g, g + n + 1, 0);
f[n] = 1;
for (int j = 30; j >= 0; j--)
if (a[n] >> j & 1) g[j] += f[n];
for (int i = n - 1; i >= 1; i--) {
for (int j = 30; j >= 0; j--)
if (a[i] >> j & 1) f[i] += g[j];
for (int j = 30; j >= 0; j--)
if (a[i] >> j & 1) g[j] += f[i];
} cout << f[1] << '\n';
}
:::::
[模拟赛] 小 Z 爱划分
给定长为
n 的序列a_i ,将其划分为若干段,权值为每一段数组元素异或和的积。求权值划分方式的得分的平方和,对
10^9+7 取模。
:::::success[题解]
记
对转移式进行拆位并观察
维护
从而
对
:::::
:::::info[代码]
const int N = 2e5 + 5, M = 31;
int n, a[N];
mint f[N], g[2][2][M][M];
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], a[i] ^= a[i - 1];
fill(f, f + n + 1, 0), memset(g, 0, sizeof(g)), f[0] = 1;
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++) g[0][0][i][j] = 1;
for (int i = 1; i <= n; i++) {
for (int x = 0; x < M; x++)
for (int y = 0; y < M; y++) f[i] += g[(a[i] >> x & 1) ^ 1][(a[i] >> y & 1) ^ 1][x][y] * (1LL << (x + y));
for (int x = 0; x < M; x++)
for (int y = 0; y < M; y++) g[a[i] >> x & 1][a[i] >> y & 1][x][y] += f[i];
} cout << f[n] << '\n';
}
:::::
P9745 「KDOI-06-S」树上异或
给定一棵
n 个点的无根树,第i 个点的点权为a_i 。选择每条边保留或不保留,设一种删边方案得到k 个连通块C_1 \sim C_k ,将方案的权值定义为\prod \limits_{i=1}^k \bigoplus \limits_{u \in C_i} a_u 。求所有
2^{n-1} 种删边方案的权值和,对998244353 取模。
:::::success[题解]
将树退化为链。记
基于拆位 DP 得到启发:
-
记
g_{u,d,x} 为满足如下条件时,所有已封闭连通块权值乘积的总和:- 只考虑
u 为根的子树。 - 二进制下,包含
u 的未封闭连通块异或和第d 位为x 。
- 只考虑
-
树形 DP 转移是逐子树加。合并子树
v 时讨论是否保留边u \to v 。-
若断开
u \to v 的边,包含v 的连通块封闭,贡献为连通块异或和。拆位优化下,贡献写作f_v=\sum_{d} g_{v,d,1} 2^d 断边后,
u 处转移g_{u,d,x} \gets g_{u,d,x} \times f_v 。 -
若保留
u \to v 的边,包含v 的连通块与u 所在的未封闭连通块合并,异或为对位运算,贡献为 DP 值相乘g_{u,d,x} \gets \sum_{y} f_{u,d,x \oplus y} \times f_{v,d,y}
-
-
DP 初值为
g_{u,d,(a_u)_d}=1 。 -
答案为
f_1=\sum \limits_{d} g_{1,d,1} 2^d 。
复杂度
:::::
:::::info[代码]
const int N = 5e5 + 5, M = 60;
int n; i64 a[N];
vector<int> e[N];
mint f[N], g[2][M][N];
void dfs(int u) {
for (int d = 0; d < M; d++) g[a[u] >> d & 1][d][u] = 1;
for (int v : e[u]) {
dfs(v);
for (int d = 0; d < M; d++) {
mint g0 = g[0][d][u], g1 = g[1][d][u];
g[0][d][u] = g0 * f[v] + g0 * g[0][d][v] + g1 * g[1][d][v];
g[1][d][u] = g1 * f[v] + g0 * g[1][d][v] + g1 * g[0][d][v];
}
}
for (int d = 0; d < M; d++) f[u] += g[1][d][u] * (1LL << d);
}
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int v = 2, u; v <= n; v++) cin >> u, e[u].emplace_back(v);
dfs(1), cout << f[1];
}
:::::