題目鏈接

解析

考慮 dp。

設 \(dp_{i,j}\) 表示長度為 \(i\) 的以 \(a_j\) 結尾的合法序列個數，于是有：

發現要求的序列長度非常長，所以考慮矩陣加速，設 \(f_{i,j}\) 表示 \(a_i\) 是否可以接在 \(a_j\) 后面，那么：

/*
*/
#include<bits/stdc++.h>
#define eps 0.000001
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 100 + 5,M = 3.2e4 + 5,mod = 1e9 + 7;
struct Matrix{
	int row,col;
	int val[N][N];
	Matrix(int r,int c){
		row = r,col = c;
		for(int i=1;i<=row;i++){
			for(int j=1;j<=col;j++){
				val[i][j] = 0;
			}
		}
	}
	friend Matrix operator * (Matrix a,Matrix b){
		Matrix c(a.row,b.col);
		for(int i=1;i<=a.row;i++){
			for(int j=1;j<=b.col;j++){
				for(int k=1;k<=a.col;k++){
					c.val[i][j] = (c.val[i][j] + 1ll * a.val[i][k] * b.val[k][j] % mod) % mod;
				}
			}
		}
		return c;
	}
	void toI(){
		for(int i=1;i<=row;i++){
			for(int j=1;j<=col;j++){
				val[i][j] = i == j;
			}
		}
	}
	void print(){
		cout<<"_______________________\n";
		for(int i=1;i<=row;i++){
			for(int j=1;j<=col;j++){
				cout<<val[i][j]<<" \n"[j==col];
			}
		}
		cout<<"_______________________\n";
	}
};
ll a[N];
Matrix qmi(Matrix a,ll b){
	Matrix res(a.row,a.col);
	res.toI();
	while(b){
		if(b & 1) res = res * a;
		a = a * a;
//		a.print();
		b >>= 1;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;
	ll k;
	cin>>n>>k;
	Matrix ori(n,1),can(n,n);
	for(int i=1;i<=n;i++){
		ori.val[i][1] = 1;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=1;j<=i;j++){
			can.val[i][j] = can.val[j][i] = __builtin_popcountll(a[i] ^ a[j]) % 3 == 0;
//			cout<<i<<" "<<j<<" "<<can.val[i][j]<<'\n';
		}
	}
	Matrix res = qmi(can,k - 1) * ori;
	int ans = 0;
	for(int i=1;i<=n;i++){
		ans = (ans + res.val[i][1]) % mod;
	}
	cout<<ans;
	return 0;
}