题解 P6569 【[NOI Online #3 提高组]魔法值（民间数据）】
一扶苏一
2020-05-24 14:24:55
## 【倍增，矩阵乘法】【P6569】魔法值
### Analysis
upd：经评论区老哥提醒，一般情况下乘法对异或没有分配律，不能直接求和变换。内容已修改。
把题目的式子写的更清晰一点：设 $e_{u, v}$ 表示 $(u, v)$ 之间是否有边，有边为 $1$，无边为 $0$，再把题目里的 $f$ 的两个下角标交换一下，即设 $f_{i, j}$ 是在第 $i$ 天，城市 $j$ 的魔法值，则有：
$$f_{i, v} = \operatorname{xor}_{u = 1}^n f_{i - 1, u} \times e_{u, v}$$
现在定义一个 $a \times b$ 矩阵 $A$ 异或一个 $b \times c$ 矩阵 $B$ 的结果为一个 $a \times c$ 的矩阵 $C$，转移为
$$C_{i, j} = \operatorname{xor}_{k = 1}^b A_{i, k} \times B_{k, j}$$
设 $1 \times n$ 矩阵 $F_i$ 的第 $1$ 行第 $j$ 列表示第 $i$ 天城市 $j$ 的魔法值，$n \times n$ 矩阵 $E$ 的第 $i$ 行第 $j$ 列表示 $i, j$ 之间是否有边，可以发现 $F_i$ 是由 $F_{i - 1}$ 异或矩阵 $E$ 转移而来。
$$F_i = F_{i - 1} \operatorname{xor} E$$
式子看起来长得很像快速幂，快速幂的要求矩阵有结合律，即 $(A \operatorname{xor} B \operatorname{xor} C)_{i, j} = (A \operatorname{xor} (B \operatorname{xor} C))_{i, j}$，来尝试推一下。（下面省略两矩阵间的 $\operatorname{xor}$ 运算符）
设 $A$ 是 $n \times p$ 矩阵，$B$ 是 $p \times q$ 矩阵，$C$ 是 $q \times m$ 矩阵，则他们的异或和为 $n \times m$ 矩阵。
$$\begin{aligned}(ABC)_{i, j} = \operatorname{xor}_{x = 1}^q(\operatorname{xor}_{y = 1}^p A_{i, y} \times B_{y, x}) \times C_{x, j} \end{aligned}$$
需要注意的是，一般情况下，乘法对异或没有分配律。例如对于 $3, 1, 2$，$3 \times (1 \operatorname{xor} 2) = 9 \neq (1 \times 3)\operatorname{xor}(2 \times 3) = 5$，因此不能直接去掉上式中的括号。
但是注意到 C 矩阵一定是一个 $01$ 矩阵（显然如果进行快速幂，那么一个 $01$ 矩阵在只做乘法和异或的情况下一定不存在进位，结果还是一个 $01$ 矩阵）。考虑当 $C_{x, j} = 0$ 或 $1$ 时，将括号去掉把 $C_{x, j}$ 乘进去，式子是成立的。证明上可以考虑当 $C_{x, j} = 0$ 时，括号乘上 $C_{x, j}$ 的结果一定是 $0$，将 $C_{x, j}$ 乘进去后，每一项都是 $0$，异或和还是 $0$；当 $C_{x, j} = 1$ 时，括号内每一项的值都没有发生改变。而整个括号的值乘上 $1$ 的值也不会改变，因此二者是相等的。
由此得到
$$\begin{aligned}(ABC)_{i, j} = \operatorname{xor}_{x = 1}^q \operatorname{xor}_{y = 1}^p A_{i, y} \times B_{y, x} \times C_{x, j} \end{aligned}$$
同理，对于 $(A(BC))_{i, j}$，也可以写出式子后用同样的证明去括号，因此二者是相等的。在 $C$ 是 $01$ 矩阵时，矩阵异或具有结合律，可以进行快速幂。
因此有
$$F_{i} = F_0 \operatorname{xor} E^i$$
这里 $E^i$ 指 $E$ 自身异或 $i$ 次。
那么有一个 naive 的做法是每次询问都进行一次矩阵快速幂，$F_{a_i} = E^{a_i}$。时间复杂度为 $O(n^3q \log a)$。期望得分 $40$ 分。
注意到对于询问，如果对 $E$ 进行快速幂的话，由于 $E$ 是 $n \times n$ 的矩阵，因此做一次的复杂度就为 $O(n^3)$。但是 $F$ 是 $1 \times n$ 的矩阵，因此 $F$ 每次异或一个 $E$ 的幂的复杂度为 $O(n^2)$。考虑不进行快速幂，对 $a_i$ 进行二进制拆分，拆成 $O(\log a)$ 个 $2$ 的幂的形式 ，首先预处理出 $E^{2^k}$ 的值，然后用 $F$ 依次乘上对应的幂即可。
预处理的复杂度为 $O(n^3 \log a)$，单次询问的复杂度为 $O(n^2 \log a)$。因此总复杂度 $O(n^3 \log a) - O(n^2q \log a)$。
另外回复一下评论区疑问，上式复杂度中的 `-` 不代表减号。对于一个算法，用 $A-B$ 表示其预处理部分为 $A$ 的复杂度，$B$ 表示其余部分的时间复杂度。
### Code
```cpp
namespace Fusu {
const int maxt = 32;
const int maxn = 105;
int n, q, m;
ll a[maxn];
struct Mat {
int x, y;
ll mt[maxn][maxn];
Mat(const int X = 0, const int Y = 0) : x(X), y(Y) {}
Mat operator*(const Mat &o) const {
Mat ret(x, o.y);
for (int i = 1; i <= x; ++i) {
for (int j = 1; j <= o.y; ++j) {
ret.mt[i][j] = 0;
for (int k = 1; k <= y; ++k) {
ret.mt[i][j] ^= mt[i][k] * o.mt[k][j];
}
}
}
return ret;
}
};
Mat g[maxt], f;
void Main() {
qr(n); qr(m); qr(q);
qra(a + 1, n);
g[0].x = g[0].y = n;
for (int u, v; m; --m) {
qr(u); qr(v);
g[0].mt[u][v] = g[0].mt[v][u] = 1;
}
for (int i = 1, di = i - 1; i < maxt; di = i++) {
g[i] = g[di] * g[di];
}
for (ll x; q; --q) {
qr(x);
f.x = 1; f.y = n;
memcpy(f.mt[1] + 1, a + 1, n * sizeof(ll));
for (ll w = 1, i = 0; w <= x; w <<= 1, ++i) if (x & w) {
f = f * g[i];
}
qw(f.mt[1][1], '\n');
}
}
} // namespace Fusu
```
看到 U 群老哥用 `bitset` 乱杀感觉好厉害啊