【倍增，矩阵乘法】【P6569】魔法值

Analysis

upd：经评论区老哥提醒，一般情况下乘法对异或没有分配律，不能直接求和变换。内容已修改。

$$f_{i, v} = \operatorname{xor}_{u = 1}^n f_{i - 1, u} \times e_{u, v}$$

$$C_{i, j} = \operatorname{xor}_{k = 1}^b A_{i, k} \times B_{k, j}$$

$$F_i = F_{i - 1} \operatorname{xor} E$$

\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}

\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}

$$F_{i} = F_0 \operatorname{xor} E^i$$

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