yukicoder : No.1958 Bit Game

こちらも割と素直。
https://yukicoder.me/problems/no/1958

問題

X要素の整数列Aと、Y要素の整数列Bが与えられる。
初期値0の変数Pに対し、以下の処理をN周繰り返す。

• Aの要素aを1つ選び、P = P or aで値を上書きする
• Bの要素bを1つ選び、P = P and bで値を上書きする

要素の選び方は(XY)^N通りあるが、最終的なPの値の総和を求めよ。

解法

2進数で考え、各桁が最終的に1になるパターンを数え上げよう。

int N,X,Y;
int A[1<<20],B[1<<20];
const ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	FOR(i,X) cin>>A[i];
	FOR(i,Y) cin>>B[i];
	ll ret=0;
	FOR(i,18) {
		int C[2]={},D[2]={};
		FOR(j,X) C[(A[j]>>i)&1]++;
		FOR(j,Y) D[(B[j]>>i)&1]++;
		
		ll from[2]={1,0};
		FOR(j,N) {
			ll to[2]={};
			to[0]=from[0]*C[0]%mo;
			to[1]=(from[1]*C[0]+from[0]*C[1]+from[1]*C[1])%mo;
			from[1]=to[1]*D[1]%mo;
			from[0]=(to[1]*D[0]+to[0]*D[1]+to[0]*D[0])%mo;
		}
		
		ret+=(1<<i)*from[1]%mo;
		
	}
	cout<<ret%mo<<endl;
}

まとめ

こちらはコードも短いね。