ABC009 D - 漸化式

概要

数列Aを下記のように定義する。数列AのM項目を答えよ。

• A[1], A[2], ..., A[K] は問題で与えられる
• A[K+N] = (C[1] AND A[K+N-1]) XOR (C[2] AND A[K+N-2]) XOR ... XOR (C[K] AND A[N]) (N ≧ 1)

制約

1 ≦ K ≦ 100
1 ≦ M ≦ 10^9
A, C は32ビット符号なし整数

方針

【ポイント①】
ANDを整数積、XORを整数和と思ったとき、漸化式は行列表記できる。（公式スライド103ページ）
https://www.slideshare.net/chokudai/abc009/103

【ポイント②】
行列の累乗もべき乗高速化が使える。（コード中のmpow）

【ポイント③】
ANDを積、XORを和とみなすことで、実際に漸化式を行列表記し、行列計算を行える。
代数学の言葉で言えば、32ビット符号なし整数はANDを「乗法」、XORを「加法」とする環をなす。
このときXORの単位元※は整数の加法と同じ0であるが、ANDの単位元はUINT_MAXであることに注意する。
（※eが演算opの単位元であるとは、演算を適用するすべてのaに対し、a op e = a となるようなeのこと）

感想

公式解説を参考にしました。（D問題解説から見れます）
https://www.slideshare.net/chokudai/abc009/56

解答

Submission #4416583 - AtCoder Beginner Contest 009

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef unsigned int ui;
typedef vector<vector<ui>> mat;
 
void print(mat A){
	rep(i, A.size()){
		rep(j, A[i].size()){
			cout << A[i][j] << (j == A[i].size()-1 ? "\n" : " ");
		}
	}
}
 
mat mmul(mat A, mat B){
	int n = A.size();
	int l = A[0].size();
	int m = B[0].size();
	mat C(n, vector<ui>(m, 0));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int k = 0; k < l; k++){
				C[i][j] ^= A[i][k] & B[k][j];
			}
		}
	}
 
	return C;
}
 
mat mE(int n){
	mat A(n, vector<ui>(n, 0));
	for(int i = 0; i < n; i++){
		A[i][i] = UINT_MAX;
	}
 
	return A;
}
 
mat mpow(mat A, int x){
	int n = A.size();
	if(x == 0) return mE(n);
	if(x & 1) return mmul(A, mpow(A, x - 1));
 
	mat B = mpow(A, x / 2);
	return mmul(B, B);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int K, M;
	cin >> K >> M;
 
	ui A[K], C[K];
	rep(i, K) cin >> A[i];
	rep(i, K) cin >> C[i];
 
	if(M <= K){
		cout << A[M-1] << endl;
		return 0;
	}
 
	int n = K;
	mat B(n, vector<ui>(n, 0));
	for(int i = 0; i < n; i++) B[0][i] = C[i];
	for(int i = 0; i < n-1; i++) B[i+1][i] = UINT_MAX;
 
	// print(mmul(B, B));
	// print(mmul(B, mE(n)));
 
	mat D(n, vector<ui>(1, 0));
	for(int i = 0; i < n; i++) D[i][0] = A[n-1-i];
 
	mat ans = mmul(mpow(B, M - n), D);
	// print(ans);
	cout << ans[0][0] << endl;
}