Xor-sequences (codeforces 691E)

Problem
You are given n integers a1,a2,...,an a 1 ,     a 2 ,     . . . ,     a n .
A sequence of integers x1,x2,...,xk 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 xi x i xor x o r xi+1 x i   +   1 ’s is a multiple of 3 and for all 1 ≤ i ≤ k. The symbol is used for the binary exclusive or operation.
How many “xor-sequences” of length k exist? Output the answer modulo 109+7 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.
Input
The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤  1018 10 18 ) — the number of given integers and the length of the “xor-sequences”.
The second line contains n integers ai (0 ≤ ai ≤  1018 10 18 ).
Output
Print the only integer c — the number of “xor-sequences” of length k modulo 109+7 10 9   +   7 .
Sample Input
5 2 15 1 2 4 8
5 1 15 1 2 4 8
Sample Output
13 5
제목 설명:
서열 a1, a2,...,an a 1 , a 2 , . . . , n, 그 중에서 k개수(중복 선택 가능)를 선택하여 서열 x1, x2,...을 구성한다.xk x 1 , x 2 , . . . , xk, xixi 이상 또는xi+1xi+1의 값을 2진법에서 1의 개수가 3의 배수(1≤i분석:
만약에 xixi가 다르거나 xi+1xi+1의 값이 2진법에서 1의 개수가 3의 배수임을 나타낸다면 xixi와xi+1xi+1은 연결할 수 있다. 즉, ii에서 i+1i+1로 이동이 존재하고 d[i][j]=1d[i][j]=1로 이동 행렬을 얻을 수 있다.전이 행렬에 대해 k-3-1k-3 1차 행렬 곱셈을 하여 최종 행렬을 얻어 최종 행렬의 모든 값을 더하면 답이 되고 행렬의 빠른 멱으로 가속한다.해석: 최종 행렬 d[i][j]=xd[i][j]=x의 의미는aiai를 시작으로 ajaj가 끝난 만족 조건의 서열 수량은 xx개이다.
AC 코드:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

const int mod = 1e9+7;

struct Matrix
{
    int n,m;
    long long d[100][100];
    Matrix (int a,int b)
    {
        n = a, m = b;
        memset(d,0,sizeof(d));
    }
    void Copy(int *tmp)
    {
        for (int i=0;ifor (int j=0;jfor (int i=0;ifor (int j=0;j0;
                for (int k=0;kif (tmp >= mod) tmp -= mod; 
                }
                c.d[i][j] = tmp;
            }
        return c;
    }
};

int n;
long long k,a[110];

int getnum(long long x)
{
    int cnt = 0;
    while (x)
    {
        cnt += x&1;
        x>>=1;
    }
    return cnt % 3;
}

void solve(long long m)
{
    Matrix A(100,100);
    for (int i=0;i1;

    Matrix B(100,100);
    for (int i=0;ifor (int j=0;jif (!getnum(a[i]^a[j])) B.d[i][j] = 1;  

    while (m)
    {
        if (m & 1) A = A*B;
        B = B*B;
        m = m>>1;
    }

    long long cnt = 0;
    for (int i=0;ifor (int j=0;jif (cnt >= mod) cnt -= mod;
        }
    printf("%lld
",cnt);
    return;
}

int main()
{
    while (scanf("%d %lld",&n,&k)!=EOF)
    {
        for (int i=0;i"%lld",&a[i]);

        if (k == 1) 
        {
            printf("%d
",n);
            continue;
        }

        solve(k-1);
    }
    return 0;
}