yukicoder : No.2171 OR Assignment

こちらも割とシンプル。
https://yukicoder.me/problems/no/2171

問題

整数列Aが与えられる。
iを選び A[i]=A[i] or A[i-1] で置き換える処理を、任意回数行えるとする。
あり得るAの組み合わせは何通りか。

以下を考える。
f(n, x) := Aのprefix n要素を定めたとき、A[n-1]=xとなるような組み合わせの数

xとしてあり得る候補を昇順ソートしたとき(B[0],B[1],....)となったとする。
A[n-1]=B[i]となる場合、A[n]はA[n], A[n]orB[0], A[n]orB[1], ... ,A[n]orB[i]のいずれかとなる。
xはnごとに高々O(log(MaxA))通りなので、O(N*log^2(maxA))程度でDPできる。

int N;
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	map<int,ll> X;
	X[0]=1;
	FOR(i,N) {
		cin>>x;
		map<int,ll> Y;
		set<int> cand={x};
		FORR2(a,b,X) {
			b%=mo;
			cand.insert(x|a);
			FORR(c,cand) Y[c]+=b;
		}
		
		swap(X,Y);
	}
	ll ret=0;
	FORR2(a,b,X) ret+=b;
	cout<<ret%mo<<endl;
}

まとめ

コードも短くていいね。