概念：和式交换

所谓和式交换的概念，大家一定都不陌生。小学就学过加法交换律，带符号搬家之说。和式交换就是基于这样的一个原理进行的一个数学技巧。

使用：数学及动规

其实数学上的做法大家一定都不陌生，再动态规划上，我们可以使用和式交换的方式优化复杂度。其表现大概为，把一种递推的分组替换为另一种较少的分组用一些和形式的优化使得复杂度降低。

这里以一道题目来看看他的具体用法。

例题：魔法门

*来源 MX

给出一个 $n$ 个点，每个点有一个点权 $a_i$ 。任意两个点 $i,j$（ $i<j$ ）之间存在魔法门共 $f(a_i \& a_j)$ 个，$f(x)$ 表示数字 $x$ 在二进制下 $1$ 的数量，$\&$ 表示按位与操作。问从 $1$ 到 $n$ 的方案数量，答案对 $998244353$ 取模。

这个题目首先一定会做的是 $O(n^2)$ 的算法。我们可以设置起点为 $i$ 终点为 $j$ ，写出状态 $dp[i]$ 表示从 $1$ 到 $i$ 的方案数。写出如下代码：

1
2
3
4
5
for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++) {
        dp[j] = (dp[j] + 1LL * dp[i] * popcount(a[i] & a[j]) % P) % P;
    }
}

而这时候想要优化这个状态，我们就需要用到和式优化的思想。由于是按位与操作，每出现一位 $1$ 就会对 $dp[j]$ 造成 $dp[i]$ 的贡献。所以说，我们可以考虑单独计算每一位的贡献，也就把原来的代码变成了：

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++) {
        for(int k = 0; k < 30; k++) {
            if(((a[i] >> k) & 1) && (a[j] >> k) & 1) {
        		dp[j] = (dp[j] + dp[i]) % P;
            }
        }
    }
}

而这一看，对于枚举的这一位是 $1$ 就能直观的看出来是转移的充要条件，所以说我们就可以把这个 for 循环提出来，而为了消去一个 $n$ 的复杂度，我们把后缀的递推变为前缀的递推，可以暂时用如下伪代码展示：

1
2
3
4
5
6
7
8
for(int j = 2; j <= n; j++) {
    for(int k = 0; k <= 30; k++) {
        if(a[j] >> k) {
            dp[j] += ... // 把这一位的总贡献统计
        }
    }
    // 维护统计总贡献的数据结构
}

这样可以保证我们的正确性，而想到方便递推，把后缀递推变为前缀递推，我们不难想到前缀和作为维护每一位的数据结构。而这里和式交换就体现出来了。我们把原来的贡献形式从下面的一式变为了二式。

这样就体现出了分组的重要，原来基于每个变量的分组，会分为 $n$ 组每组只有至多 $30$ 个数据。但是和式变化后就变为了按照位数分组，$30$ 组但是可以同时处理 $n$ 个数据，复杂度就可以得到降低。 我们设置 $sum[i][j]$ 表示 $1$ 到 $i$ 这些点中，第 $j$ 位为一的点的价值总和

那么代码就会变为：

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int j = 2; j <= n; j++) {
    for(int k = 0; k <= 30; k++) {
        if(a[j] >> k) {
            dp[j] += sum[j - 1][k];
        }
    }
    for(int k = 0; k <= 30; k++) {
        sum[j][k] = sum[j - 1][k];
        if(a[j] >> k) {
            sum[j][k] = sum[j][k] + dp[j];
        }
    }
}

这就是和式变换的做法，比较灵活，需要一定的随机应变能力。