C++14(g++5.4) 解法, 执行用时: 581ms, 内存消耗: 15592K, 提交时间: 2019-04-16 20:09:43

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=5e5+5; 
int a[maxn];
typedef long long ll;
ll dis[maxn],n;
struct node{
	int id;
	ll dis;
	bool operator<(const node&a)const{
		return dis>a.dis;
	}
};
const int mod=19260817;
priority_queue<node>Q;
int mark[maxn];
int qpow(int a,int b){
	int c=1;
	while (b){
		if (b&1)
			c=1ll*a*c%mod;
		b>>=1;
		a=1ll*a*a%mod;
	}
	return c;
}
int get(int u,int v,int q){
	return qpow(max(u,v),1<<q)+1;
}
int main(){
	memset(dis,0x3f3f3f,sizeof(dis));
	memset(mark,-1,sizeof(mark));
	cin >> n;
	for (int i=1;i<=n;i++)
		cin >> a[i];
	for (int i=1;i<=n;i++){
		dis[a[i]]=0;
		if (mark[a[i]]!=-1){
			cout << 0 ;
			return 0;
		}
		mark[a[i]]=a[i];
		Q.push({a[i],0});
	}
	ll ans=1e18+5;
	while (!Q.empty()){
		node U=Q.top();
		Q.pop();
		int u=U.id;
		ll d=U.dis;
		if (ans<d) continue;
		if (d!=dis[u]) continue;
		for (int i=0;i<18;i++){
			int v=u^(1<<i),p=get(u,v,i);
			if (mark[u]!=mark[v]){
				ans=min(ans,dis[u]+dis[v]+p);
			}
			if (dis[u]+p<dis[v]){
				dis[v]=dis[u]+p;
				Q.push({v,dis[v]});
				mark[v]=mark[u];
			}
		}
	}
	cout << ans;
}

C++11(clang++ 3.9) 解法, 执行用时: 3171ms, 内存消耗: 24164K, 提交时间: 2019-04-13 15:48:49

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,int>PI;
const int N=262150,M=18,K=10000000;
const ll inf=1LL<<60;
int n,i,j,x,vis[N],w[N][M];
ll f[N],ans=inf;
int q[K],h,t;
bool in[N];
inline int po(int a,int b){
  int W=19260817;
  int t=1;
  for(;b;b>>=1,a=1LL*a*a%W)if(b&1)t=1LL*t*a%W;
  return (t%W+W)%W;
}
inline void ext(int x,ll y){
  if(f[x]<=y)return;
  f[x]=y;
  if(in[x])return;
  in[x]=1;
  if(y<f[q[h]])q[--h]=x;else q[++t]=x;
}
int main(){
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&x);
    if(vis[x])return puts("0"),0;
    vis[x]=1;
  }
  int m=18;
  n=1<<m;
  for(i=0;i<n;i++)for(j=0;j<m;j++)w[i][j]=po(max(i,i^(1<<j)),1<<j)+1;
  for(i=0;i<m;i++){
    for(j=0;j<n;j++)f[j]=inf,in[j]=0;
    h=K/2;
    t=h-1;
    for(j=0;j<n;j++)if(vis[j])if(j>>i&1)ext(j,0);
    while(h<=t){
      int x=q[h++];
      in[x]=0;
      for(j=0;j<m;j++)ext(x^(1<<j),f[x]+w[x][j]);
    }
    for(j=0;j<n;j++)if((j>>i&1)==0&&vis[j])ans=min(ans,f[j]);
  }
  printf("%lld",ans);
}