比赛 |
20120323 |
评测结果 |
AAAAAAAAAA |
题目名称 |
放棋子 |
最终得分 |
100 |
用户昵称 |
恢复用户700 |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2012-03-23 21:41:43 |
显示代码纯文本
(*
Problem : examtwo
Author : whitetooth
Start Time : 2012-3-23 20:53
Finish Time : 2012-3-23 21:17
Result :
Method : Dynamic Programming
*)
Program Examtwo;
Const
maxn=80+5; maxk=20; maxs=1<<9;
Var
a,b :array[0..maxn] of int64;
f :array[0..maxn,0..maxk,0..maxs] of int64;
n,m,k,i :longint;
ans,temp :int64;
Procedure Swap(Var x,y:longint);
Var temp :longint;
Begin
temp:=x; x:=y; y:=temp;
End;
Procedure Init;
Begin
read(n,m,k);
if k>n*m then
begin
writeln('0/0');
close(input); close(output);
halt;
end;
if n<m then swap(n,m);
End;
Procedure Dfs(x,y,s,prev,now:longint;u:int64);
Var up,left :longint;
Begin
if s>k then exit;
if y>m then
begin
f[x,s,now]:=f[x,s,now]+u;
exit;
end;
dfs(x,y+1,s,prev,now,u); //不放置
up:=prev and (1<<(y-1));
if y>1 then left:=now and (1<<(y-2))
else left:=0;
if (up=0)and(left=0) then
begin
now:=now or (1<<(y-1));
dfs(x,y+1,s+1,prev,now,u);
end;
End;
Procedure Main;
Var j,l :longint;
Begin
f[0,0,0]:=1;
for i:=0 to n-1 do
for j:=0 to k do
for l:=0 to 1<<m-1 do
begin
if f[i,j,l]=0 then continue;
dfs(i+1,1,j,l,0,f[i,j,l]);
end;
End;
Function Gcd(x,y:int64):int64;
Begin
if y=0 then exit(x)
else exit(gcd(y,x mod y));
End;
Procedure Print;
Var j,p :longint;
Begin
for i:=0 to 1<<m-1 do ans:=ans+f[n,k,i];
temp:=1;
for i:=n*m-k+1 to n*m do a[i]:=i;
for i:=1 to k do b[i]:=i;
for i:=n*m-k+1 to n*m do
begin
for j:=1 to k do
begin
p:=gcd(a[i],b[j]);
a[i]:=a[i] div p;
b[j]:=b[j] div p;
end;
temp:=temp*a[i];
end;
p:=gcd(ans,temp);
ans:=ans div p;
temp:=temp div p;
writeln(temp,'/',ans);
End;
Begin
Assign(input,'examtwo.in'); reset(input);
Assign(output,'examtwo.out'); rewrite(output);
Init;
Main;
Print;
Close(input); close(output);
End.