yukicoder : No.3550 Another Rurumaru Function Problem

これはまぁ解けた。
https://yukicoder.me/problems/no/3550

問題

F(x,y)の値は、２進数表記で2^iの桁は、

• iが偶数の場合、xとyの2^iの桁のAND
• iが奇数の場合、xとyの2^iの桁のOR

で定義される。
整数列Aが与えられる。
Aの空でない部分列のうち、F()を使い全要素foldした値の最大値は何か。

解法

G(mask) := Aのうち、iが偶数のbitの2^iの集合が、maskを包含するようなAの部分集合における、iが奇数のbitの2^iの桁のORを取った値
とする。G(mask)を高速ゼータ変換で求めたうえで、maskを総当たりしよう。

int N;
int A[202020];

int ma[1<<15];
int num[1<<15];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		x=y=0;
		FOR(j,15) {
			x|=((A[i]>>(j*2))%2)<<j;
			y|=((A[i]>>(j*2+1))%2)<<j;
		}
		ma[x]|=y;
		num[x]++;
	}
	int mask;
	FOR(i,15) FOR(mask,1<<15) if(mask&(1<<i)) {
		ma[mask^(1<<i)]|=ma[mask];
		num[mask^(1<<i)]+=num[mask];
	}
	
	int ret=0;
	FOR(mask,1<<15) if(num[mask]) {
		int v=0;
		FOR(i,15) {
			if(mask&(1<<i)) v|=1<<(2*i);
			if(ma[mask]&(1<<i)) v|=1<<(2*i+1);
		}
		ret=max(ret,v);
	}
	cout<<ret<<endl;
	
	
}

まとめ

ここはまだすんなり。