Codeforces ECR #139 : E. Decomposition

Eまでは苦戦しつつもどうにか解いている。
https://codeforces.com/contest/1766/problem/E

問題

0123で構成される整数列Xに対し、f(X)は以下のように定義する。
初期状態で、数列のリストがあり、そのリストは空である。
Xの先頭から順に、要素vを以下のようにリストに追加していくことを考える。

• リスト内の数列のうち、vを加えてもandが正であり続ける数列があれば、そのうち先頭に追加する。
• そのような数列がなければ、vだけからなる数列を新規に作りリストに追加する。

f(X)は最終的なリスト内の数列の個数とする。
Xの全連続部分列X'に対し、f(X')の総和を求めよ。

解法

リスト中、bitwise-andを取った値のうち非0なものは高々3つしかできない。
よって、DPでそのような値の並び順を状態として持ち、数え上げて行こう。

int N;
ll from[4][4][4];
ll to[4][4][4];
ll ret=0;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	FOR(i,N) {
		cin>>j;
		ZERO(to);
		ll s=0;
		FOR(x,4) FOR(y,4) FOR(k,4) if(from[x][y][k]) {
			s+=from[x][y][k];
			if(j&x) {
				to[j][y][k]+=from[x][y][k];
			}
			else if(j&y) {
				to[x][j][k]+=from[x][y][k];
			}
			else if(j&k) {
				to[x][y][j]+=from[x][y][k];
			}
			else {
				ret+=from[x][y][k]*(N-i);
				if(j==0) {
					to[x][y][k]+=from[x][y][k];
				}
				else {
					if(x==0) to[j][y][k]+=from[x][y][k];
					else if(y==0) to[x][j][k]+=from[x][y][k];
					else if(k==0) to[x][y][j]+=from[x][y][k];
					else {
						assert(0);
					}
				}
			}
		}
		to[j][0][0]++;
		ret+=(N-i);
		swap(from,to);
	}
	//FOR(x,4) FOR(y,4) FOR(k,4) ret+=from[x][y][k];
	cout<<ret<<endl;
}

まとめ

例が丁寧ではあるけど、その分なんか長いな。