Codeforces ECR #014 : E. Xor-sequences

なんだこれ。
http://codeforces.com/contest/691/problem/E

問題

N要素の数列A[i]が与えられる。
これらの要素を使い別のK要素の数列Xを作りたい。(Xの各要素はAのいずれかでなければならない)

その際、隣接要素に対しX[i] xor X[i+1]を2進数表記したとき、1のbitの立つ数が3の倍数であるようにしたい。
そのようなXは何通りあるか。

解法

以下のN次正方行列を考える。
M(i,j) := A[i] xor A[j]を2進数表記したとき、1のbitの立つ数が3の倍数であるなら1、そうでないなら0
これは言い換えると末尾がA[i]の数列に、さらにその後ろにA[j]を追加可能かどうかを示す。

Xの最初の値はなんでもよく、その後(K-1)個A[i]の要素を追加すると考えると、M^(K-1) * B (Bは全要素1のベクトル)を求め、その総和を求めればよい。
行列累乗はバイナリ法で解こう。

int N;
ll K;
ll A[101];
ll mat[101][101][70];
ll vec[101];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>K;
	K--;
	FOR(i,N) cin>>A[i];
	FOR(x,N) FOR(y,N) mat[x][y][0]=(__builtin_popcountll(A[x]^A[y])%3==0);
	
	FOR(i,N) vec[i]=1;
	FOR(i,61) {
		FOR(x,N) FOR(y,N) FOR(z,N) (mat[x][y][i+1] += mat[x][z][i]*mat[z][y][i])%=mo;
		
		if(K & (1LL<<i)) {
			ll vec2[101];
			FOR(j,N) vec2[j]=vec[j], vec[j]=0;
			FOR(x,N) FOR(y,N) (vec[x] += vec2[y]*mat[y][x][i])%=mo;
		}
	}
	
	ll ret=0;
	FOR(i,N) ret+=vec[i];
	cout<<ret%mo<<endl;
	
}

まとめ

条件は無駄にややこしいけど、結局行列累乗に持ち込むことされわかれば典型。