codeforces 691E Xor-sequences 矩阵快速幂

思路：刚开始 n个元素,a[i][j]代表以i开头，j结尾的二元组符合条件的有多少

        这是等于长度为2的数量 长度为3的数量为a*a，所以长度为n的数量是a^(k-1)

        然后就是矩阵快速幂，然而我并不能发现这道题是矩阵快速幂，没办法，太弱了

注：这个模板是从Q神的AC代码里扒下来的，仰慕Q神

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e2+5;
const LL mod = 1e9+7;

LL a[105],n,k; 
struct Matrix{
  LL a[N][N];
  Matrix(){
    memset(a,0,sizeof(a));
  }
  void init(){
    for(int i=1;i<=n;++i)a[i][i]=1;
  }
  Matrix operator *(const Matrix &rhs)const{
     Matrix ret;
     for(int i=1;i<=n;++i)
      for(int j=1;j<=n;++j)
        for(int k=1;k<=n;++k)
          ret.a[i][j]=(ret.a[i][j]+a[i][k]*rhs.a[k][j]%mod)%mod;
      return ret;
  }
  Matrix operator ^(LL mi)const{
    Matrix tmp=(*this),ret;
    ret.init();
    while(mi){
      if(mi&1)ret=ret*tmp;
      tmp=tmp*tmp;
      mi>>=1;
    }
    return ret;
  }
};

int main(){
  scanf("%I64d%I64d",&n,&k);
  for(int i=1;i<=n;++i)
    scanf("%I64d",&a[i]);
  Matrix cur;
  for(int i=1;i<=n;++i){
    for(int j=1;j<=n;++j)
      if(__builtin_popcountll(a[i]^a[j])%3==0)
        ++cur.a[i][j];
  }
  cur=cur^(k-1);
  LL ret=0;
  for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
      ret=(ret+cur.a[i][j])%mod;
  printf("%I64d
",ret);
  return 0;
}