Explanation

Notice that we're asked to count the total number of paths, so we can store the graph as an adjacency matrix by setting $A_{i, j}=1$ if the number of bits $x_i \oplus x_j$ is divisible by $3$. After constructing these edges, notice that this is the same problem as CSES - Graph Paths(solution), except we query the sum of all the paths.

Then, we can calculate $A^k$ in $\mathcal{O}(N^3\log K)$ using Matrix Exponentiation.

Our final answer is:

Implementation

Time Complexity: $\mathcal{O}(N^3\log K)$

Copy
#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) {