2n2Srj - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
constexpr int mod = 1e9+7, LG = 20, N = 1<<LG;
int a[N], dp_recursive[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;
}

int solve(int mask) {
    if (~dp_recursive[mask]) return dp_recursive[mask];
    dp_recursive[mask] = a[mask];
    for(int msk=(mask-1)&mask; msk; msk=(msk-1)&mask)
        dp_recursive[mask] = (dp_recursive[mask] + solve(msk)) % mod;
    int down = (fp(2, __builtin_popcount(mask)) + mod - 1) % mod;
    return dp_recursive[mask] = dp_recursive[mask] * fp(down, mod -2) % mod;
}

signed main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
    memset(dp_recursive, -1, sizeof dp_recursive);

    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;

    std::cout << solve((1<<n)-1) << '\n';
}