题目链接：Luogu P1896/BZOJ 1087/LibreOJ 2153/SCOI2005 D2T2。

一道 状压 \(\texttt{dp}\) 的入门题目，或者一道简单的打表题。

未完待续（时空限制）。

题目

题目描述

在 $N\times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。

数据范围

变量	数据范围
\(N\)	\(1\leq N\leq 9\)
\(K\)	\(0\leq K\leq N^2\)

时空限制

题目编号	时间限制	空间限制
$$\text{Luogu}:1\text{s}/125\text{MiB}$$
$$\text{BZOJ}:10\text{s}/162\text{MiB}$$
$$\text{LibreOJ}:1\text{s}/256\text{MiB}$$

题解

解法 A（状压 \(\texttt{dp}\)）

思路

考虑到数据范围 $1\leq n\leq 9$，不妨用二进制数 $x$ 来表示某一行的放置状态，用 $f_{i,j,S}$ 表示当第 $i$ 行状态为 $j$ 时，已经放置了 $S$ 个国王的总方案数。

那么有：
\[f_{i,j,S}=\sum f_{i-1,k,T}\]

然后可以得出：
\[\text{ans}=\sum f_{n,i,K}\]

代码

状压 \(\texttt{dp}\) 的代码略。

解法 B（打表）

思路

考虑 $1\leq n\leq 9,0\leq k\leq n^2$，计算得出，输入总共有 $\sum^9_{i=1}i\times(i^2+1)=2070$ 种可能，比较少，所以选择打表，用解法 A 打表，实现快速输出答案。

代码

渐进时间复杂度为 $\Theta(1)$ 的程序。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; //本题答案超过了 int 范围

const ll ans[10][82]={
{}, //空开 ans[0][]
{1,1},
{1,4,0,0,0},
{1,9,16,8,1,0,0,0,0,0},
{1,16,78,140,79,0,0,0,0,0,0,0,0,0,0,0,0},
{1,25,228,964,1987,1974,978,242,27,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,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},
{1,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},
{1,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},
{1,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},
}; //打成的表

int n,K;

int main(void){
    scanf("%d%d",&n,&K); //读入
    printf("%lld\n",ans[n][K]); //输出
    return 0;
}