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;
}