自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:22:01，当前版本为作者最后更新于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

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 乱杀感觉好厉害啊