Xor-sequences

题意翻译

Problem Description 给定一个数集A，现在你需要构造一个长度为k的序列B，序列B的元素从数集A中任意挑选，要求B中任意相邻的两个数字的异或值二进制表示中1的个数是3的倍数，请问B的有多少种合法的构造方案？两种方案不同当且仅当存在Bi在A中的位置不同。 Input 第一行两个数字n和k，表示数集大小和序列B的长度， 接下来一行有n个数字，代表数集中的元素。 40%的数据：1≤n≤100，1≤k≤10000，0≤ai≤10^18 100%的数据：1≤n≤100，1≤k≤10^18，0≤ai≤10^18 Output 输出一行，表示答案，由于答案可能会很大，请对10^9+7取模后输出。

题目描述

You are given \$ n \$ integers \$ a_{1},a_{2},...,a_{n} \$ . A sequence of integers \$ x_{1},x_{2},...,x_{k} \$ is called a "xor-sequence" if for every \$ 1<=i<=k-1 \$ the number of ones in the binary representation of the number \$ x_{i} \$ ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF691E/081f686069870b762728923799c454e27369af9a.png) \$ x_{i+1} \$ 's is a multiple of \$ 3 \$ and ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF691E/187abd20483c4318d7cd71518f323b9990bcdd61.png) for all \$ 1<=i<=k \$ . The symbol ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF691E/081f686069870b762728923799c454e27369af9a.png) is used for the binary exclusive or operation. How many "xor-sequences" of length \$ k \$ exist? Output the answer modulo \$ 10^{9}+7 \$ . Note if \$ a=[1,1] \$ and \$ k=1 \$ then the answer is \$ 2 \$ , because you should consider the ones from \$ a \$ as different.

输入输出格式

输入格式

The first line contains two integers \$ n \$ and \$ k \$ ( \$ 1<=n<=100 \$ , \$ 1<=k<=10^{18} \$ ) — the number of given integers and the length of the "xor-sequences". The second line contains \$ n \$ integers \$ a_{i} \$ ( \$ 0<=a_{i}<=10^{18} \$ ).

输出格式

Print the only integer \$ c \$ — the number of "xor-sequences" of length \$ k \$ modulo \$ 10^{9}+7 \$ .

输入输出样例

输入样例 #1

``````5 2
15 1 2 4 8
``````

输出样例 #1

``````13
``````

输入样例 #2

``````5 1
15 1 2 4 8
``````

输出样例 #2

``````5
``````