yukicoder : No.1443 Andd

こちらは余り迷わず。
https://yukicoder.me/problems/no/1443

問題

N個の正整数A[i]が与えられる。
変数Xがあり、初期値は0である。
各A[i]に対し、

• X = X + A[i]
• X = X and A[i]

のいずれかによりXの値を更新することを考える。
処理毎に、Xの取りえる値は何通りあるか求めよ。
ただし、Aは1024未満の非負整数である。

解法

後者の演算の結果は、常に0～1023になる。
また、前者の演算の結果は、演算前の結果が異なるなら演算後も必ず異なる。

そこで、Xが0～1023である可能性の有無と、C[i] = (X mod 1024がiであるような、1024以上のXの取りえる値の数)としてそれぞれを数えていこう。

int N;
int fu[1024],fo[1024];
int tu[1024],to[1024];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	fu[0]=1;
	FOR(i,N) {
		cin>>x;
		ZERO(to);
		ZERO(tu);
		FOR(j,1024) {
			if(fu[j]) {
				tu[j&x]=1;
				if(j+x>=1024) {
					to[(j+x)&1023]++;
				}
				else {
					tu[j+x]=1;
				}
			}
			if(fo[j]) {
				tu[j&x]=1;
				to[(j+x)&1023]+=fo[j];
			}
		}
		swap(to,fo);
		swap(tu,fu);
		int sum=0;
		FOR(j,1024) sum+=fo[j]+fu[j];
		cout<<sum<<endl;
	}
}

まとめ

★2.5でもいいかもね。