691E - Xor-sequences - CodeForces Solution

#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
using namespace std;
using LL = long long;
using VL = vector<LL>;
const int P = 1e9 + 7;
struct Mat {
	int m, n;
	vector<VL> F;
	Mat(int _n, int _m) : n(_n), m(_m), F(n, VL(m)) {}
	Mat operator * (const Mat& x) const {
		Mat ans(n, x.m);
		_for(r, 0, n) _for(c, 0, x.m) _for(i, 0, m) 
			(ans.F[r][c] += F[r][i] * x.F[i][c] % P) %= P;
		return ans;
	}
	Mat operator ^ (LL k) const {
		Mat ans = *this, p = *this;
		for (--k; k; k >>= 1, p = p * p)
			if (k & 1) ans = ans * p;
		return ans;
	}
};
int main(void) {
	ios::sync_with_stdio(false), cin.tie(0);
	LL n, k; cin >> n >> k, k--;
	vector<LL> A(n);
	for (LL& a : A) cin >> a;
	if (k == 0) { cout << n << "\n"; return 0; }
	Mat G(n, n), F(n, 1);
	_for(i, 0, n) _for(j, 0, n)
		G.F[i][j] = __builtin_popcountll(A[i] ^ A[j]) % 3 == 0;
	_for(i, 0, n) F.F[i][0] = 1;
	F = (G ^ k) * F;
	LL ans = 0;
	_for(i, 0, n) (ans += F.F[i][0]) %= P;
	cout << ans << "\n";
	return 0;
}