https://codeforces.com/contest/449/problem/D (INCLuSION EXCLUSION principle), C++ (gcc)

https://codeforces.com/contest/449/problem/D (INCLuSION EXCLUSION principle)

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
typedef long long int ll;

const int mod = 1e9 + 7;

const int N = 1 << 20;

ll fast_pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return ans;
}

int dp[2][N] = {0};

int SOS_DP(){
    // for each 'x' count the distinct 'Ai' such that 'Ai&x = x'
    // from main function itself we set dp[0][x] as the count of x occured in the input array (i.e. it is dp[-1][x])
    
    int prv = 0, cur = 1;
    for(int j = 0; j < 20; j++){
        for(int i = 0; i < N; i++)
            if(i & (1 << j)) dp[cur][i] = dp[prv][i];
            else dp[cur][i] = dp[prv][i] + dp[prv][i ^ (1 << j)];
            
        swap(prv, cur);
    }
    
    //for(int j = 0; j < 8; j++) cout << dp[prv][j] << " ";cout << endl;
    return prv;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    memset(dp, 0, sizeof(dp));
    
    int n;
    cin >> n;
    for(int j = 0; j < n; j++){
        int x;
        cin >> x;
        dp[0][x]++;
    }
    int i = SOS_DP();
    
    ll rev_ans = 0;
    for(int j = 1; j < N; j++){
        int bits = 0;
        for(int k = 0; k < 20; k++) if(j & (1 << k)) bits++;
        
        if(bits % 2) rev_ans = (rev_ans + (fast_pow(2, dp[i][j]) - 1 + mod) % mod) % mod;
        else rev_ans = (rev_ans - (fast_pow(2, dp[i][j]) - 1 + mod) % mod + mod) % mod;
    }
    
    ll ans = (fast_pow(2, n) - 1 + mod - rev_ans + mod) % mod;
    cout << ans << endl;
    return 0;
}


run \| edit \| history \| help	0