岗哨布防计数

普及-⏱ 500ms💾 256MB#P3285🏷️ 动态规划状态压缩DP

题目描述

在 $n \times n$ 的方形场地上布置 $k$ 座岗哨。岗哨可监视相邻的 $8$ 个格子, 任意两座岗哨不能处在互相监视的位置上。求合法的布置方案总数。

输入格式

一行两个整数 $n$ 和 $k$($1 \le n \le 16$,$0 \le k \le n \times n$)。

输出格式

一行一个整数:合法布置方案总数。

数据范围

None

样例输入 #1
3 2
样例输出 #1
16
样例输入 #2
4 4
样例输出 #2
79