#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <ctime>
using std::min;
using std::max;
//a rewrite for vector<int>
struct vi
{
int l,a[9];
const int& operator[](int u) const {return a[u];}
int& operator[](int u) {return a[u];}
};
inline bool operator < (const vi&a,const vi&b)
{
for(int i=0;i<a.l;++i) if(a[i]!=b[i]) return a[i]<b[i];
return 0;
}
inline bool operator == (const vi&a,const vi&b)
{
for(int i=0;i<a.l;++i) if(a[i]!=b[i]) return 0;
return 1;
}
std::vector<vi> g[13];
inline void dfs(int x,int u,const vi&c,int*w)
{
++w[u];
if(c[x]&u)
for(int o=c[x]&u;o;o^=o&-o)
dfs(__builtin_ctz(o),u^(o&-o),c,w);
}
inline void dfsf(int x,int u,const vi&c,int*w)
{
++w[u];
if((~c[x])&u)
for(int o=(~c[x])&u;o;o^=o&-o)
dfsf(__builtin_ctz(o),u^(o&-o),c,w);
}
int main()
{
g[0].push_back(vi());
for(int i=0;i<9;++i)
{
for(auto t:g[i])
{
int m1=0,m=0;
for(int j=0,r;j<i;++j)
{
if((r=__builtin_popcount(t[j]))>m1) m=0,m1=r;
if(r==m1) m|=1<<j;
}
for(int e=0;e<(1<<i);++e) if(__builtin_popcount(e)>m1
||(__builtin_popcount(e)==m1&&((e&m)==m))) //ensure the node has the highest degree
{
vi u; u.l=i+1;
for(int p=0;p<=i;++p) //enumerate position
{
bool s=(p==0); int x;
#define yield(l,c) do{if((x=(c))>u[l]&&!s) goto skip; else s|=x<u[l],u[l]=x;}while(0)
for(int a=0;a<p;++a)
yield(a,((t[a]>>p)<<(p+1))|(t[a]&((1<<p)-1))|((!((e>>a)&1))<<p));
yield(p,((e>>p)<<(p+1))|(e&((1<<p)-1)));
for(int a=p;a<i;++a)
yield(a+1,((t[a]>>p)<<(p+1))|(t[a]&((1<<p)-1))|((!((e>>a)&1))<<p));
skip:;
#undef yield
}
g[i+1].push_back(u);
}
}
sort std::sort(g[i+1].begin(),g[i+1].end());
g[i+1].erase(std::unique(g[i+1].begin(),g[i+1].end()),g[i+1].end());
int sz=g[i+1].size();
std::vector<vi> h(sz);
#pragma omp parallel for
for(int w=0;w<sz;++w)
{
vi u=g[i+1][w],v;
auto sw=[&](int x,int y) {
std::swap(v[x],v[y]);
for(int s=0;s<v.l;++s)
{
int&o=v[s];
if(((o>>x)^(o>>y))&1) o^=(1<<x)|(1<<y);
}
};
for(int x=0;x<=i;++x)
for(int y=x+1;y<=i;++y)
{
{v=u;sw(x,y);u=min;u=std::min(u,v);}
for(int z=y+1;z<=i;++z)
{
{v=u;sw(x,y);sw(y,z);u=min;u=std::min(u,v);}
{v=u;sw(x,y);sw(x,z);u=min;u=std::min(u,v);}
{v=u;sw(y,z);sw(x,z);u=min;u=std::min(u,v);}
{v=u;sw(y,z);sw(x,y);u=min;u=std::min(u,v);}
{v=u;sw(x,z);sw(x,y);u=min;u=std::min(u,v);}
{v=u;sw(x,z);sw(y,z);u=min;u=std::min(u,v);}
}
{v=u;sw(x,y);u=min;u=std::min(u,v);}
}
h[w]=u;
}
sort std::sort(h.begin(),h.end());
h.erase(std::unique(h.begin(),h.end()),h.end());
g[i+1]=h;
}
std::cout<<"pre ("<<clock()*1./CLOCKS_PER_SEC<<"s)\n";
for(int o=0;o<=9;++o)
{
int mx=0;
const int s=g[o].size();
#pragma omp parallel for reduction(max:mx)
for(int t=0;t<s;++t)
{
int a[9<<9],b[9<<9];
memset(a,0,sizeof(int)*(o<<o));
memset(b,0,sizeof(int)*(o<<o));
for(int i=0;i<o;++i)
dfs(i,((1<<o)-1)^(1<<i),g[o][t],a+(i<<o)),
dfsf(i,((1<<o)-1)^(1<<i),g[o][t],b+(i<<o));
int r[9][9],c=(1<<o)-1,vx[1<<9];
for(int p=0;p<o;++p)
{
int*A=a+(p<<o),vn=0;
for(int x=0;x<=c;++x) if(A[x]) vx[vn++]=x;
for(int q=0;q<o;++q) if(p!=q)
{
int*B=b+(q<<o),su=0;
for(int u=0;u<vn;++u)
su+=A[vx[u]]*B[c^vx[u]];
r[p][q]=su;
}
}
int m1=0,m=0;
for(int j=0,pc;j<o;++j)
{
if((pc=__builtin_popcount(g[o][t][j]))>m1) m=0,m1=pc;
if(pc==m1) m|=1<<j;
}
for(int i=0;i<(1<<o);++i) if(__builtin_popcount(i)>m1
||(__builtin_popcount(i)==m1&&((i&m)==m)))
{
int tot=(o==0);
for(int j=0;j<o;++j)
if(i&(1<<j))
{
tot+=a[j<<o];
for(int ii=c^i;ii;ii^=ii&-ii)
tot+=r[j][__builtin_ctz(ii)];
}
else tot+=b[j<<o];
mx=max mx=std::max(mx,tot);
}
}
std::cout<<"a("<<o+1<<") = "<<mx<<" ("<<clock()*1./CLOCKS_PER_SEC<<"s)\n";
}
}
Try it online! (barely fits the timer)Try it online!
pre (5.137s632s)
a(1) = 1 (5.138s634s)
a(2) = 1 (5.139s635s)
a(3) = 3 (5.14s636s)
a(4) = 5 (5.141s637s)
a(5) = 15 (5.141s638s)
a(6) = 45 (5.142s638s)
a(7) = 189 (5.142s639s)
a(8) = 661 (5.144s642s)
a(9) = 3357 (5.234s736s)
a(10) = 15745 (2021.434s756s)
