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