Xor-sequences

Explicación

Nótese que se nos pide contar el número total de caminos, así que podemos guardar el grafo como una matriz de adyacencia poniendo $A_{i, j}=1$ si el número de bits de $x_i \oplus x_j$ es divisible por $3$ . Después de construir estas aristas, nótese que este es el mismo problema que CSES - Graph Paths (solución), excepto que consultamos la suma de todos los caminos.

Luego, podemos calcular $A^k$ en $\mathcal{O}(N^3\log K)$ usando exponenciación de matrices.

Nuestra respuesta final es:

\sum_{i=0}^N \sum_{j=0}^N A_{i, j}^k

Implementación

Complejidad temporal: $\mathcal{O}(N^3\log K)$

C++


#include <bits/stdc++.h>
using namespace std;
 
const long long MOD = 1e9 + 7;
 
template <class T> struct Matrix {
	vector<vector<T>> v;
	void init(int n, int m) { v = vector<vector<T>>(n, vector<T>(m)); }
 
	Matrix operator*(Matrix b) {
		int x = v.size();
		int y = v[0].size();
		int z = b.v[0].size();
		assert(y == sz(b.v));
		Matrix<T> ret;
		ret.init(x, z);
		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				for (int k = 0; k < z; k++) {
					ret.v[i][k] += v[i][j] * b.v[j][k];
					ret.v[i][k] %= MOD;
				}
			}
		}
		return ret;
	}
};
 
int main() {
	long long n, m;
	cin >> n >> m;
	m--;
	vector<long long> v(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	Matrix<long long> A, B;
	A.init(n, n);
	B.init(n, n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (__builtin_popcountll(v[i] ^ v[j]) % 3 == 0) { A.v[i][j] = 1; }
		}
	}
 
	Matrix<long long> ret;
	ret.init(n, n);
	for (int i = 0; i < n; i++) { ret.v[i][i] = 1; }
	for (long long b = m; b > 0; b /= 2) {
		if (b & 1) { ret = ret * A; }
		A = A * A;
	}
 
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ans += ret.v[i][j];
			ans %= MOD;
		}
	}
	cout << ans << '\n';
}