拆位优化 DP

· · 算法·理论

一个比较简单的 trick,用于优化转移与位运算有关的 DP。

下文记 (x)_d 为 x 二进制下第 d 位。

P4310 绝世好题

定义序列 b_i 是优美的,当且仅当 \forall 1 \le i<|b|, b_i \text { and } b_{i+1} \ne 0。

给定一个长为 n 的序列 a_i,求出最长优美子序列长度。

:::::success[题解]

我们有经典的 O(n^2) DP,记 f_i 为以 a_i 结尾的最长优美子序列长度,转移枚举上一个元素 a_j 得

f_i=1+\max_{j<i \land a_i \text { and } a_j \ne 0} f_j

记 (a_i)_d 为 a_i 二进制下第 d 位,枚举到 a_i 时我们维护

\begin{aligned} g_d=\max_{j<i \land (a_j)_d=1} f_j \end{aligned}

从而

\begin{aligned} f_i&=1+\max_{j<i \land a_i \text { and } a_j \ne 0} f_j\\ &=1+\max_{j<i, \exists d, (a_i)_d=(a_j)_d=1} f_j\\ &=1+\max_{d} \max_{j<i \land (a_i)_d=(a_j)_d=1} f_j\\ &=1+\max_{(a_i)_d=1} g_d \end{aligned}

转移顺序为先 f \to g 再 g \to f 的辗转 chkmax。

复杂度 O(n \log V)。

:::::

:::::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[题解]

记 f_i 为 i \to n 的路径数。模拟 DAG 上 DP 易得转移式

f_i=\sum_{j=i+1}^n f_j \times \text{popcount}(a_i \text{ and } a_j)

考察上式的组合意义:每个 (a_i)_d=(a_j)_d=1 的 d 导出一次 f_j \to f_i 的转移。据此设

g_d=\sum_{j=i+1}^n [(a_j)_d=1] f_j

从而在转移到 i 时

\begin{aligned} f_i&=\sum_{j=i+1}^n f_j \sum_{d} [(a_i)_d=(a_j)_d=1]\\ &=\sum_{(a_i)_d=1} \sum_{j=i+1}^n [(a_j)_d=1]f_j\\ &=\sum_{(a_i)_d=1} g_d \end{aligned}

复杂度 O(n \log V)。

:::::

:::::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[题解]

记 s_i 为 a_i 的前缀异或和。O(n^2) DP 显然,记 f_i 为前缀 1 \sim i 的答案,枚举上一个划分点 j 有

f_i=\sum_{j=0}^{i-1} f_j (s_i \oplus s_j)^2

对转移式进行拆位并观察

\begin{aligned} f_i&=\sum_{j=0}^{i-1} f_j \left(\sum_{x} [(s_i)_x \ne (s_j)_x] 2^x\right)^2\\ &=\sum_{j=0}^{i-1} f_j \sum_x \sum_y [(s_i)_x \ne (s_j)_x][(s_i)_y \ne (s_j)_y]2^{x+y}\\ &=\sum_{x,y} 2^{x+y} \sum_{j=0}^{i-1} [(s_i)_x \ne (s_j)_x][(s_i)_y \ne (s_j)_y] f_j \end{aligned}

维护

g_{x,y,p,q}=\sum_{j=0}^{i-1} [(s_j)_x = p][(s_j)_y=q]f_j, p,q \in \{0,1\}

从而

f_i=\sum_{x,y} 2^{x+y} g_{x,y,1-(s_i)_x,1-(s_i)_y}

对 f,g 辗转转移,复杂度 O(n \log^2 V)。

:::::

:::::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[题解]

将树退化为链。记 s_i 为 a_i 的前缀异或和,暴力 DP 是 f_i=\sum \limits_{j=0}^{n-1} f_j (s_i \oplus s_j),拆位优化为 g_{d,x}=\sum \limits_{j=0}^{n-1} [(s_j)_d=1] f_j,复杂度 O(n \log V)。

基于拆位 DP 得到启发:

复杂度 O(n \log V)。

:::::

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

:::::