今日份题意杀已到帐，请注意查收
还是只会爆搜，枚举当前还没有选的位，当前这一轮的贡献是 \(\frac{minn+maxn}{2}\)
但考虑这样一个事情
如果当前情况下反打表CPU选第 \(i\) 位更优，那不管轮到哪个CPU都一定会选它，只不过填的数相反
而这一轮由每个CPU填数的概率是 \(\frac{1}{2}\)
也就是在说地址的每一位都是随机的
所以最后选中每个位置的概率相等
直接输出 \(\frac{\sum\limits_{i=0}^{2^k-1} |a_i-a_{ans}|}{2^k}\) 即可
Code:
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long
#define fir first
#define sec second
#define make make_pair
#define reg register int
//#define int long long
char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
int ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
return ans*f;
}
int k, ans;
ll rom[1<<18];
const ll p=1e9+7, inv2=500000004;
namespace force{
struct pair_hash{inline size_t operator () (pair<int, int> p) const {return hash<int>()(p.fir*p.sec);}};
unordered_map<pair<int, int>, pair<double, ll>, pair_hash> mp{10000, pair_hash()};
pair<double, ll> dfs(int s, int t) {
//cout<<"dfs1 "<<s<<' '<<t<<endl;
if (s==(1<<k)-1) return make(llabs(rom[ans]-rom[t]), llabs(rom[ans]-rom[t])%p);
if (mp.find(make(s, t))!=mp.end()) return mp[make(s, t)];
pair<double, ll> t1, t2, mx=make(0, 0), mn=make(1e18, 0);
for (reg i=0; i<k; ++i) if (!(s&(1<<i))) {
t1=dfs(s|(1<<i), t), t2=dfs(s|(1<<i), t|(1<<i));
if (t1.fir>mx.fir) mx=t1;
if (t1.fir<mn.fir) mn=t1;
if (t2.fir>mx.fir) mx=t2;
if (t2.fir<mn.fir) mn=t2;
}
pair<double, ll> tem=make(0.5*mx.fir+0.5*mn.fir, (inv2*mx.sec%p+inv2*mn.sec%p)%p);
mp[make(s, t)]=tem;
return tem;
}
}
namespace task1{
ll qpow(ll a, ll b) {
ll ans=1;
while (b) {
if (b&1) ans=ans*a%p;
a=a*a%p; b>>=1;
}
return ans;
}
void solve() {
ll sum=0;
for (int i=0; i<(1<<k); ++i) sum=(sum+llabs(rom[i]-rom[ans]))%p;
sum=sum*qpow(1<<k, p-2)%p;
printf("%lld\n", sum);
exit(0);
}
}
signed main()
{
k=read(); ans=read();
for (reg i=0,n=1<<k; i<n; ++i) rom[i]=read();
//printf("%lld\n", dfs(0, 0).sec);
task1::solve();
return 0;
}