Codeforces #902 : Div1 B. Effects of Anti Pimples

不参加だった回。
https://codeforces.com/contest/1876/problem/B

問題

N要素の整数列Aが与えられる。
Aの各要素は初期状態で白だとする。
ここで、いくつかの要素を黒く塗る。その後、白要素のうち、indexが黒要素の倍数の要素は緑色に塗る。
この時、Aのスコアは黒または緑で塗られた色の最大ととする。

黒く塗る要素(2^N-1)通りに対するスコアの総和を求めよ。

解法

各1要素sを黒く塗った場合、indexがその倍数であるものを総当たりしてその範囲にある最大値をB(s)とする。
また、sを1～Nまで走査したとき、B(s)の個数をC(B(s))とする。

スコアがxになるのは、B(s)がxより大きいsが1個も選ばれず、B(s)=xとなるsが1個以上選ばれる場合なので、その積を計上していけばよい。

int N,A[101010],B[101010];
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i+1];
	}
	for(i=1;i<=N;i++) {
		for(j=i*2;j<=N;j+=i) A[i]=max(A[j],A[i]);
		B[A[i]]++;
	}
	
	ll ret=0;
	int sum=0;
	for(i=0;i<=100000;i++) if(B[i]) {
		(ret+=i*modpow(2,sum)%mo*(modpow(2,B[i])-1))%=mo;
		sum+=B[i];
	}
	cout<<ret<<endl;
	
}

まとめ

これは割とシンプル。