|
物理好き |
|
#48819
C言語にて、再帰を利用して、かつ、一番上の行を1 2 3 4 ... Nに固定して一番左の列を1 2 3 4 ... Nになるように並べ替えることを仮定したうえで最後に (N! * (N-1)!) を掛けるという方針で実装すると、N=7までは手元のPCでも充分高速(1分未満)に求められました #include<stdio.h> long long factorial(long long x){ long long i,r=1; for(i=x;i>=1;i--){ r*=i; } return r; } long long n; long long res=0; long long row[16][16]={0},column[16][16]={0}; long long latin_sq[16][16]; void rec(long long a,long long b){ if(b==n){a++;b=0;} if(a==n){res++;return;} long long i; for(i=1;i<=n;i++){ if(a==0 && b!=(i-1)){continue;} if(b==0 && a!=(i-1)){continue;} if(row[a][i]==1 || column[b][i]==1){continue;} row[a][i]=1;column[b][i]=1; latin_sq[a][b]=i; rec(a,b+1); row[a][i]=0;column[b][i]=0; } } int main(){ scanf("%lld",&n); rec(0,0); printf("%lld\n",res*factorial(n)*factorial(n-1)); } それ以上は組み合わせ爆発の例に使われるくらいには値が肥大化してしまいますね… https://oeis.org/A002860 https://en.wikipedia.org/wiki/Combinatorial_explosion |
|
大阪府
3月1日（日） 19:30:31
MAIL:butsuri.0523@gmail.com HomePage:Twitter 48823 |