题解 P6569 【[NOI Online #3 提高组]魔法值（民间数据）】

· · 题解

【倍增，矩阵乘法】【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 乱杀感觉好厉害啊