比赛 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.