5PBLb1 - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
constexpr int mod = 1e9+7, LG = 20, N = 1<<LG;
int a[N], dp[N], c[N];

long long fp(long long b, int e){
    if(e) return fp(b*b% mod, e>>1) * (e&1?b:1) % mod;
    return 1;
}

signed main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    for(int i=0; i<n; ++i)
        std::cin >> a[1<<i];

    for(int i=0; i<LG; ++i)
        for(int mask=0; mask<N; ++mask)
            if(mask & (1<<i))
                a[mask] = (a[mask] + a[mask^(1<<i)]) % mod;

    for(int k=1; k<=LG; ++k){
        memset(c, 0, sizeof c);
        for(int mask = 0; mask < N; ++mask)
            if(__builtin_popcount(mask) == k)
                c[mask] = dp[mask] = ((a[mask] + dp[mask]) % mod) * fp((fp(2, k)+mod-1)%mod, mod-2) % mod;

        for(int bit = 0; bit < LG; ++bit)
            for(int mask = 0; mask < N; ++mask)
                if(mask & (1<<bit))
                    c[mask] = (c[mask] + c[mask ^ (1<<bit)]) % mod;

        for(int mask = 0; mask < N; ++mask)
            if(__builtin_popcount(mask) > k)
                dp[mask] = (dp[mask] + c[mask]) % mod;
    }

    std::cout << dp[(1<<n)-1] << '\n';
}