yukicoder : No.2082 AND OR XOR

割と頭がこんがらがる。
https://yukicoder.me/problems/no/2082

問題

整数N,A,B,Cが与えられる。
2項演算子*を次のように定める。
x*y = (A×(x AND y) + B×(x OR y) + C×(x xor y)) % 4

各要素が0～3の整数値を取る整数列Nのうち、左から順に2項演算子を使って畳み込んだ値と、右から畳み込んだ値が一致するのは何通りか。

解法

左からの畳み込みは普通に行いつつ、右の畳み込みは先読みする形でDPする。
dp(n, L, R0, R1, R2, R3) := Nの先頭n要素まで決めたとき、左から順に畳み込んだ値がLで、右に0,1,2,3が来た時、右に畳み込んだ値がR0,R1,R2,R3となるようなものの組み合わせ
として、次に来る値0,1,2,3を総当たりすればよい。

int N,A,B,C;
int M[4][4];

ll from[4][4][4][4][4];
ll to[4][4][4][4][4];
const ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>C;
	FOR(x,4) FOR(y,4) M[x][y]=(A*(x&y)+B*(x|y)+C*(x^y))%4;
	
	FOR(x,4) from[x][M[0][x]][M[1][x]][M[2][x]][M[3][x]]=1;
	int a,b0,b1,b2,b3;
	FOR(r,N-2) {
		ZERO(to);
		FOR(a,4) FOR(b0,4) FOR(b1,4) FOR(b2,4) FOR(b3,4) FOR(x,4) {
			int B[4]={b0,b1,b2,b3};
			(to[M[x][a]][B[M[0][x]]][B[M[1][x]]][B[M[2][x]]][B[M[3][x]]]+=from[a][b0][b1][b2][b3])%=mo;
		}
		swap(from,to);
	}
	ll ret=0;
	FOR(a,4) FOR(b0,4) FOR(b1,4) FOR(b2,4) FOR(b3,4) FOR(x,4) {
		int B[4]={b0,b1,b2,b3};
		if(M[a][x]==B[x]) ret+=from[a][b0][b1][b2][b3];
	}
	cout<<ret%mo<<endl;
}

まとめ

数式のややこしさに一瞬びっくりするけど、そこは本質でもない。