cfgym100792E

201708 （ACM）数学----组合数学

• 求 [i < j，在第x层] 贡献的次数即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<"="<<a<<endl;
#define dd(a) cout<<#a<<"="<<a<<" ";
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int N=(1<<18)+20;
const ll mod=1e9+7;
int k,n;
int a[N];
ll mu[N],in[N],sum[20][N];
ll kpow(ll a,ll b) {
    ll res=1;
    while(b) {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll inv(ll a) {
    return kpow(a,mod-2);
}
ll C(ll a,ll b) {
    if(a<b) return 0;
    return mu[a]*in[b]%mod*in[a-b]%mod;
}
void init() {
    mu[0]=1;
    rep(i,1,N) mu[i]=mu[i-1]*i%mod;
    in[N-1]=inv(mu[N-1]);
    for(int i=N-2;~i;--i) in[i]=in[i+1]*(i+1)%mod;
    rep(x,0,k) {
        for(int j=n;j;--j) {
            ll t=1ll*a[j]*C(n-j,(1<<x)-1)%mod;
            sum[x][j]=(sum[x][j+1]+t)%mod;
        }
    }
}
int main() {
    scanf("%d",&k);n=(1<<k);
    rep(i,1,n+1) scanf("%d",a+i);
    init();
    ll ans=0;
    rep(x,0,k) {
        rep(i,1,n+1) {
            int t=(1<<x);
            int tt=(((n>>x)-2)>>1)+1;
            ll res=sum[x][i+1]*a[i]%mod*C(n-i-t,t-1)%mod*mu[t]%mod*mu[t]%mod;
            res=res*tt%mod*2%mod*mu[n-t*2]%mod;
            ans=(ans+res)%mod;
        }
    }
    printf("%lld\n",ans*in[n]%mod);
    return 0;
}