Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
3 2
Sample Output
16
状压dp，用三进制表示状态，以下是标准程序
program bzoj1087;
var
ans:int64;
o,n,i,j,k:longint;
tot:array [0..1] of longint;
thr:array [0..10] of longint;
dl:array [0..1,0..200001] of record
stu,count:longint;
end;
f:array [0..1,0..31,0..19683] of int64;
exi:array [0..31,0..19683] of boolean;
procedure dfs (no,now,count,stu:longint;p:int64);
var
x:longint;
begin
if count>k then exit;
if no>n then
begin
if not exi[count,now] then
begin
exi[count,now]:=true;
f[o,count,now]:=0;
inc(tot[o]);
dl[o,tot[o]].count:=count;
dl[o,tot[o]].stu:=now;
end;
f[o,count,now]:=f[o,count,now]+p;
exit;
end;
x:=stu div thr[no-1] mod 3 - 1;
if x<0 then x:=0;
dfs(no+1,now+x*thr[no-1],count,stu,p);
x:=stu div thr[no-1] mod 3;
if x<2 then
begin
x:=now;
if no>1 then
x:=x-x div thr[no-2] mod 3 * thr[no-2] + 2 * thr[no-2];
x:=x-x div thr[no-1] mod 3 * thr[no-1] + 2 * thr[no-1];
if no<n then
x:=x-x div thr[no] mod 3 * thr[no] + 2 * thr[no];
dfs(no+2,x,count+1,stu,p);
end;
end;
begin
read(n,k);
if n=1 then
begin
if k<=1 then writeln(1)
else writeln(0);
exit;
end;
if k*3>n*n then
begin
writeln(0);
exit;
end;
thr[0]:=1;
for i:=1 to 10 do
thr[i]:=thr[i-1]*3;
o:=0;
tot[o]:=1;
for i:=0 to n-1 do
dl[o,1].stu:=dl[o,1].stu+thr[i];
f[o,0,dl[o,1].stu]:=1;
for j:=1 to n do
begin
o:=o xor 1;
fillchar(exi,sizeof(exi),false);
tot[o]:=0;
for i:=1 to tot[o xor 1] do
dfs(1,0,
dl[o xor 1,i].count,
dl[o xor 1,i].stu,
f[o xor 1,dl[o xor 1,i].count,dl[o xor 1,i].stu]);
end;
for i:=1 to tot[o] do
if dl[o,i].count=k then
ans:=ans+f[o,dl[o,i].count,dl[o,i].stu];
writeln(ans);
end.
然后我生成了下表，排到了rank1
const quick:array [1..9,1..81] of int64=( (1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (9,16,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (16,78,140,79,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (25,228,964,1987,1974,978,242,27,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (36,520,3920,16834,42368,62266,51504,21792,3600,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (49,1020,11860,85275,397014,1220298,2484382,3324193,2882737,1601292,569818,129657,18389,1520,64,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (64,1806,29708,317471,2326320,12033330,44601420,119138166,229095676,314949564,305560392,204883338,91802548,25952226,4142000,281571,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0), (81,2968,65240,962089,10087628,77784658,450193818,1979541332,6655170642,17143061738,33787564116,50734210126,57647295377,49138545860,31122500764,14518795348,4959383037,1237072414,224463798,29275410,2673322,163088,6150,125,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0) ); var n,k:longint; begin read(n,k); writeln(quick[n,k]); end.