CS Academy And Closure

リンク : https://csacademy.com/contest/archive/task/and-closure/statement/

問題概要

長さNの数列が与えられて、個の部分集合のすべてをandで計算したときの数字の種類は何種類か求めよ。

解説

一見簡単そうに見えたが実は罠。dp[i]をiの集合を部分集合としてもつ数字をすべて&したときの数と置くと、dp[i]=iのときはiが答えに含まれることになる。そこで、それぞれの数字の部分集合を列挙して計算しようとすると、それぞれ、x<=10⁶よりΣ[k=0~20]{2^k20Ck}かかり、これは3.5×10⁹くらいになりTLEとなる。そこでiを部分集合としてもつdpをしたいと考えると、高速ゼータ変換にたどり着く。高速ゼータ変換の解説はここではできないので省略する。簡単に話すと、1??を4を部分集合としてもつ集合とあらわすとすると、A[i]のすべてのiについて求まっているとき、dp[i] (iは1と?の集合)に関して計算がO(n2ⁿ)(nはビット数)でできるということ。
急に問題の難易度上がってびっくりした。あと海外でこれはSOS dpっていうのかもしれない。

LL n, a[110000], ans, dp[1<<21];
int main() {
    cin >> n;
    rep(i, n) {
        cin >> a[i];
        dp[a[i]] = a[i];
    }
    rep(i, 1<<21) {
        if(dp[i]==0)
        dp[i] = (1 << 21) - 1; 
    }
    dp[0] = 0;
    rep(i, 21) rep(b, 1 << 21)
        if (0 == (b & (1 << i))) dp[b] &= dp[b | (1 << i)];
    rep(i, 1100000)if (dp[i] == i)ans++;
    cout << ans << endl;
    return 0;
}