2017-10-24

ABC009 - D 漸化式

解説

D - 漸化式

問題概要

二つの数列 A1,A2,,AKA_1, A_2, …, A_KC1,C2,,CKC_1, C_2, …, C_K が入力で与えられる。

数列 A は以下の式によって計算できる。

AN+K=(C1ANDAN+K1)XOR(C2ANDAN+K2)XORXOR(CKANDAN)A_{N+K}=(C_1 AND A_{N+K−1}) XOR (C_2 AND A_{N+K−2}) XOR …  XOR (C_K AND A_N)

数列 A の M 番目の値を求めよ。

解き方

漸化式を計算するには、DPを使えば良いです。しかし、制約が大きく、DPでは解けません。 別の方法を使って漸化式を解く必要があります。

そこで、行列累乗を使います(あり本 P.180参照)。 行列累乗に and や xor が使えるのかですが、それは atcoder の公式解説を参照してください。 あり本を見ながらやれば実装できます。ほとんどあり本のプログラムそのままです。 正しい順番で値を入れて、正しい値で初期化して、演算子を変えましょう。

ただ、割と引っかかるポイントが多かったです。

気をつけるところ

  • and は論理積

bit の and が取りたい時は、 bitand か & を使いましょう。

  • 各項の順番

行列に値を入れる際、右から左に並べるのか、左から右に並べるのか(もちろん上下も)。

  • and 演算子の単位元

普通に掛け算をするのであれば、単位元は 1 です。 あり本にあるプログラムや式は、行列の掛け算を行うため、 単位元に 1 が使われています。 しかし、この問題では and 演算子を使うため、単位元は全 bit が 1 の値です。 初期化ミスに気をつけましょう。

  • m ≤ k の時の処理

m ≤ k の時は、与えらえれた入力をそのまま返せば良いです。 入力を行列累乗のために逆順に持っていたことを忘れるとWAです(2敗)。

実装

#define int long long なので、単位元は -1 を使っています。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

#define int long long
typedef vector<vector<int>> mat;

mat mul(mat &a, mat &b){
	mat c(a.size(), vector<int>(b[0].size()));
	rep(i,a.size()){
		rep(k,b.size()){
			rep(j,b[0].size()){
				c[i][j] = (c[i][j] xor (a[i][k] bitand b[k][j]));
			}
		}
	}
	return c;
}

mat pow(mat a, int n){
	mat b(a.size(), vector<int>(a.size(),0));
	rep(i,b.size()) b[i][i] = -1;
	while(n > 0){
		if(n & 1) b = mul(b,a);
		a = mul(a, a);
		n >>= 1;
	}
	return b;
}

int solve(int n, mat A, vector<int> c){
	mat a(A.size(), vector<int>(A.size(), 0));
	for(int i = c.size() - 1; i >= 0; i--){
		//a[0][i] = c[A.size() - 1 - i]; ここの順番が逆だった。
		a[0][i] = c[i];
	}
	rep(i,c.size() - 1){
		a[i + 1][i] = -1;
	}

	a = pow(a,n); //行列Aのn乗。
	mat res = mul(a, A);
	return res[0][0];
}

signed main(){
	int k, m;
	cin >> k >> m;

	mat a(k, vector<int>(1));
	vector<int> c(k);
	rep(i,k) cin >> a[k - i - 1][0];
	rep(i,k) cin >> c[i];
	
	if(m <= k){
		cout << a[k - m][0] << endl;
	}else{
		cout << solve(m - k,a,c) << endl; //-kを忘れずに
	}
}