/* C++ program to calculate A057981 Author: M. Wang Email Address: atvv@foxmail.com Compiler: MinGW compiler Compiler Version: v4.9.2 (tdm64-1) OEIS URL: https://oeis.org/A057981 */ #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 __int64 mp; unsigned row[64]; unsigned ub; unsigned n; unsigned __int64 p3[64]; unsigned __int64 factorial(unsigned n){ unsigned i; unsigned __int64 ans=1; for(i=2;i<=n;i++){ ans*=i; } return ans; } 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=-invcnt; per_dfs(k+1); if(t==1)invcnt=-invcnt; } 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=-invcnt; per_dfs(k+1); if(t!=1)invcnt=-invcnt; swap(str[i],str[k]); } } } else{ detval+=invcnt; } } void det(int sum1){ detval=0; per_dfs(0); int tmp; tmp=abs(detval); if(tmp){ mp+=1<<sum1; } } void dfs(int idx,int sum1){ if(idx==0){ int st=row[n1]/p3[n2]*p3[n2]; for(row[0]=min(st,row[idx+1])-1;row[idx]>0;row[idx]--) { det(sum1+row[0]/p3[n1]); } return; } for(row[idx]=row[idx+1]-1;row[idx]>0;row[idx]--) { dfs(idx-1,sum1+row[idx]/p3[n1]); } } 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++) { if(n>1){ mp=0; ub=2*p3[n-1]; 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]--){ //fprintf(stderr,"(%d)\n",row[n1]); dfs(n1-1,1); } } else{ mp=n+1; } //Number of singular n X n (-1,0,1)-matrices printf("%"I64"u\n",p3[n*n]-mp*(factorial(n))); } return 0; }