CS Academy Maxor
リンク : https://csacademy.com/contest/archive/task/maxor/statement/
問題概要
N個の数字が与えられ、任意の二つの数字をorで計算したときの最大値とこの最大値となる通り数を求めよ。
解説
これもまた高速ゼータ変換...dp1[i]をiを部分集合としてもつ数字の個数とする。これは高速ゼータ変換で簡単に求められる。次に、dp2[i]をiとNこの数字それぞれに&をしたときの最大値とする。この問題の最大値の答えをmとすると、m=max{ {i=1,2,...N}{A[i] or dp2[~A[i]]} }となる。これを求めるほうが、通り数を求めるより難しかった。dp1[i]の数字が正のときはdp2[i]=iとなる。それ以外の場合はdp2[i]=max{ {j=0,1..17}{if(i&(1<<j))dp2[i xor (1<<j)]} }となる。
LL n, ans, dp1[1 << 20], dp2[1 << 20], a[110000]; int main() { cin >> n; rep(i, n) { cin >> a[i]; dp1[a[i]] += 1; dp2[a[i]] = a[i]; } rep(i, 20) rep(b, 1LL << 20) if (0 == (b & (1LL << i))) { dp1[b] += dp1[b | (1LL << i)]; } rep(b, 1LL << 20)if (dp1[b] > 0)dp2[b] = b; Rrep(i, 20) rep(b, 1LL << 20) if ((b & (1LL << i))) { dp2[b] = max(dp2[b], dp2[b ^ (1LL << i)]); } LL mx = 0; rep(i, n) { mx = max(mx, a[i] | dp2[((1LL << 20) - 1)^ a[i] ]); } rep(i, n) { if (mx == a[i]) { ans += dp1[0] - 1; } else if ((mx&a[i]) == a[i]) { ans += dp1[mx - a[i]]; } } cout <<mx<<" "<< ans/2 << endl; return 0; }