今天遇到很不爽的事情了，然後就接著刷Usaco
USACO，latin。大概意思是要求n階（2<=n<=7）的拉丁方的數量（就是用1-n排成n*n的方陣，然後每行和每列中每個數字只能出現一次）。要求拉丁方第一行為{1，2，3，...，n}。
似乎同樣是可以簡單的cheat的，，，顯然看範圍~
BScheaters~
這道題~很囧的是，n《=6時brute force DFS仍然很快，但是n=7就嚴重TLE了~好多人都是預先跑個20s得到答案再cheat的~其實沒有必要，維基百科有答案~BSing。
主要用到一個群論的變換函數，把第一二行看做置換運算，用一個hash。
題解說的不完全是~它是用
(2，2)處填上3-n的方案完全一樣。
1. A latin square whose first row and column are both {1, 2, 3 ... N} is called a reduced (or normalized) latin square. It is useful because for any latin square, permutating its rows and columns will produce many different latin squares. Let L(K) represe
nt the number of KxK reduced latin square and N(K) represent the total number of KxK latin square, it is obvious that
N(K) = L(K) * N! * (N-1)!
since for any reduced latin square, you can permute its rows (N!) and columns ((N-1)!) and get N!*(N-1)! different latin squares. Likewise, M(K) = L(K) * (N-1)! where M(K) is the number of KxK latin square of our interest. Therefore, we only need to searc
h and count the reduced latin square.
2. For the second row (the first row is {1, 2, 3 ... N}): the number of latin square (reduced or not reduced) whose row 2 column 2 is 3 is same with number of latin square whose row 2 column 2 is 4, 5, or ... N. We can take advantage of this fact; the idea is better illustrated in the code below.
3. When we filled the kth row of a latin square (k<N), we know for a fact that the (k+1)th row could be filled. Therefore, we only need to search until N-1 row.
同樣用了編譯開關優化~我愛編譯開關~
{
TASK: latin
LANG: PASCAL
ID: awesome5
}
{$A+,B-,D-,E-,F-,G+,I-,L-,N+,O-,P+,Q-,R-,S-,T-,V-,X+,Y-}
{$ M 65520,0,655360}
//for tripley
//by phoeagon
//DF-search with pruning of Polya counting
type
sqre=array[0..7,0..7]of longint;
sqrr=array[0..7,0..7]of longint;
var
pos,clt:sqre;
row,col:sqrr;
n,count,cty:longint;
ct:qword;
bd:longint;
inde:array[0..7,0..20]of longint;
procedure hash(const a:longint;var count,len:longint);inline;
var
v:Array[0..7]of boolean;
i,curt,point,curlen:longint;
begin
fillchar(v,sizeof(v),0);
len:=1;count:=0;
for i:=1 to n do
if not v[pos[a-1,i]]then
begin
point:=i;curt:=pos[a-1,i];
//lt:=false;
inc(count);curlen:=0;
while not v[curt]do
begin
v[curt]:=true;
// begin
curt:=pos[a,point];
point:=clt[a-1,curt];
//end;
//lt:=lt xor true;
inc(curlen);
end;
len:=len*curlen;
end;
//writeln(count,' ',len);
end;
{procedure prn;inline;
var
i,j:longint;
begin
writeln(count,' :');
for i:=1 to n do
begin
for j:=1 to n do
writE(pos[i,j],' ');
writeln;
end;
hash(2,i,j);writeln(i,' ',j);
end;}
procedure chg(const a,b,c,delta:longint);inline;
var
i:longint;
begin
inc(row[a,c],delta);inc(col[b,c],delta);
end;
procedure init;inline;
var
i,j:longint;
begin
fillchar(inde,sizeof(inde),255);
reaD(n);
for i:=1 to n do
begin pos[1,i]:=i;clt[1,i]:=i;end;
for i:=1 to n do
begin pos[i,1]:=i;clt[i,1]:=i;end;
for i:=1 to n do
inc(row[i,i]);
{for j:=2 to n do
inc(toc[j,i,i]);}
for j:=1 to n do
inc(col[j,j]);
//chg(j,i,j,1);
//toc[j,i]:=toc[j,i]or(1 shl j);
if n=2 then bd:=2 else bd:=n-1;
end;
procedure dfs(const a,b,c:longint{;const toc:sqre});inline;
var
i,j,x:longint;done:boolean;
tmp:longint;
len,cout:longint;
begin
done:=false;
if (row[a,c]<>0)or(col[b,c]<>0) then
exit;
//toc[a,b]:=toc[a,b]or(1 shl c);
//chg(a,b,c,1);
pos[a,b]:=c;clt[a,c]:=b;
chg(a,b,c,1);
if (a=2)and(b=n)then
begin
hash(2,len,cout);
//prn;
//writeln(len,' ',cout,' ',c);
if inde[len,cout]>=0 then
begin
inc(count,inde[len,cout]);
//writeln('@@@:) ',inde[len,cout]);
chg(a,b,c,-1);
exit;
end
else begin tmp:=count;
//writeln(inde[len,cout]);
end;
end;
if b=n then
if (a=bd) then
begin inc(count);//writeln(count);
//prn;
//writeln(pos[3,2]);
done:=true;{solution found}end
else begin
i:=a+1;j:=2;
end
else begin i:=a;j:=b+1;end;
if not done then
for x:=1 to n do
//if toc[i,j,x]<>0 then
dfs(i,j,x);
//toc[a,b]:=toc[a,b]xor(1 shl c);
chg(a,b,c,-1);
//tmp:=0;
if (a=2)and(b=n)then
//if count<>tmp then
begin
inde[len,cout]:=count-tmp;
//writeln('inde[',len,',',cout,']=',inde[len,cout]);
end;
end;
function pw(a:longint):longint;inline;
var
re:longint;
begin
re:=1;
while a>1 do
begin
re:=re*a;
dec(a);
end;
exit(re);
end;
procedure work;inline;
var
x:longint;
begin
//for x:=1 to n do
dfs(2,2,1);
cty:=count;count:=0;
dfs(2,2,3);
count:=count*(n-2)+cty;
//writeln(count);
ct:=pw(n-1);
//ct:=trunc(exp(ln(n-1)/ln(2)));
ct:=ct*count;
writeln(ct);
end;
begin
assign(input,'latin.in');reset(input);
assign(output,'latin.out');rewrite(output);
init;
work;
close(output);
end.
|
