[题解] P6569 [NOI Online #3 提高组] 魔法值

P6569 [NOI Online #3 提高组] 魔法值

不放简要题意了，题面写的很简要。

看到数据范围自然可以想到矩阵快速幂优化。但乘法对异或没有分配律。所以直接拆位，把异或变成加法对二取模就有分配律了。

还有一个优化就是提前预处理出矩阵的 2 的幂次方，然后询问时直接二进制分解乘起来就行。

时间复杂度 \(O\left(\dfrac{n^3 \log a + n^2 \log^2 a}{w}\right)\)。

constexpr int MAXN = 1e2 + 9, MAXLG = 32;
int n, m, q;
ui f0[MAXN];

struct Matrix {
	int n, m;
	bitset<MAXN> mat[MAXN];
	
	Matrix() { return; }
	Matrix(int _n, int _m): n(_n), m(_m) {
		for (int i = 1; i <= n; i ++)
			mat[i].reset();
		return;
	}
	friend Matrix operator * (const Matrix &x, const Matrix &y) {
		Matrix ans(x.n, y.m); assert(x.m == y.n);
		for (int i = 1; i <= x.n; i ++)
			for (int j = 1; j <= x.m; j ++)
				if (x.mat[i][j]) ans.mat[i] ^= y.mat[j];
		return ans;
	}
	Matrix& operator *= (const Matrix &x) { return (*this) = (*this) * x; }
} f, G[MAXLG];

void slv() {
	n = Read<int>(), m = Read<int>(), q = Read<int>();
	f = Matrix(1, n);
	for (int i = 1; i <= n; i ++) f0[i] = Read<ui>();
	G[0] = Matrix(n, n);
	for (int i = 1; i <= m; i ++) {
		int u = Read<int>(), v = Read<int>();
		G[0].mat[u][v] = G[0].mat[v][u] = 1;
	}
	for (int i = 1; i < 32; i ++) G[i] = G[i - 1] * G[i - 1];
	while (q --) {
		ui a = Read<ui>();
		ui ans = 0;
		for (int i = 0; i < 32; i ++) {
			Matrix f(1, n);
			for (int j = 1; j <= n; j ++) f.mat[1][j] = f0[j] >> i & 1;
			for (int k = 0; k < 32; k ++) if (a >> k & 1) f *= G[k];
			if (f.mat[1][1]) ans += 1u << i;
		}
		Write(ans, '\n');
	}
	return;
}