/* C++ program to calculate A306838 Author: M. Wang Email Address: atvv@foxmail.com Compiler: MinGW compiler Compiler Version: v4.9.2 (tdm64-1) OEIS URL: https://oeis.org/A306838 Output: 1 3 5 9 25 67 233 ... */ #include <iostream> #include <ctime> #include <cassert> #include <cstring> #include <vector> #include <string> #include <set> #include <map> using namespace std; #define lenof(a)(sizeof(a)/sizeof(a[0])) #define min(a,b) (((a)<(b))?(a):(b)) #define max(a,b) (((a)>(b))?(a):(b)) #define min_(a,b) {if(a>(b))a=(b);} #define max_(a,b) {if(a<(b))a=(b);} #if defined _MSC_VER || defined __MINGW32__ #define I64 "I64" #else #define __int64 long long #define I64 "ll" #endif set<unsigned __int64> mp; unsigned row[64]; unsigned ub; unsigned n; unsigned __int64 p3[64]; int mx; int n2; int n1; int str[64]; int invcnt=1; int detval; void per_dfs(int k){ int i; if(k!=n){ int t=row[k]/p3[str[k]]%3; if(t){ if(t!=1)invcnt*=-1; per_dfs(k+1); if(t!=1)invcnt/=-1; } for(i=k+1;i<n;i++){ t=row[k]/p3[str[i]]%3; if(t){ swap(str[i],str[k]); if(t!=1)invcnt*=1; else invcnt*=-1; per_dfs(k+1); if(t!=1)invcnt/=1; else invcnt/=-1; swap(str[i],str[k]); } } } else{ detval+=invcnt; } } void det(){ detval=0; per_dfs(0); mp.insert(abs(detval)); } void dfs(int idx){ if(idx==0){ for(row[0]=row[idx+1]-1;row[idx]>0;row[idx]--){ det(); } return; } for(row[idx]=row[idx+1]-1;row[idx]>0;row[idx]--){ dfs(idx-1); } } void init_p3(){ int i; p3[0]=1; for(i=1;i<lenof(p3);i++){ p3[i]=p3[i-1]*3; } } int main(int argc,char ** argv){ init_p3(); for(n=0;;n++){ mp.clear(); if(n==0){ mp.insert(0); } else if(n==1){ mp.insert(0); mp.insert(1); } else{ ub=p3[n]; n1=n-1; n2=n-2; int i; for(i=0;i<n;i++){ str[i]=i; } for(row[n1]=ub-1;row[n1]/p3[n1];row[n1]--){ dfs(n2); } } printf("%u\n",2*mp.size()-1); } return 0; }