【题目描述】
原题来自：SGU 223
在 n×n 的棋盘上放 k 个国王，国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数。
【输入】
只有一行，包含两个整数 n 和 k。
【输出】
每组数据一行为方案总数，若不能够放置则输出 0。
【输入样例】
3 2【输出样例】
16【提示】
样例输入 2
4 4样例输出 2
79数据范围与提示：
对于全部数据，1≤n≤10,0≤k≤n^2 。
一、 题意转换
本题本质上是求解在一个满足特定“邻域互斥限制”（即任意两个元素不能在相邻的 8 个格子中共存）的棋盘上，放置k个不可分辨元素的合法组合方案总数。
二、 思考过程与解题思路
面对这道题，我们是如何一步步推导出最优解的？
1. 为什么第一直觉的暴力不可行？如果是初学者，第一直觉肯定是dfs回溯暴力搜索：遍历棋盘的每一个格子，枚举“放”或“不放”。 但我们算一笔物理算力的账：当N = 10时，棋盘有 100 个格子。暴力搜索的时间复杂度是惊人的，必然超时。
2. 破局核心：为什么一定会想到“状态压缩 DP”？很多同学以为用状压是因为“数据范围小（）”。错！数据范围小仅仅是物理算力允许我们用状压的“客观通行证”，而逼着我们必须用状压的绝对核心动机，是为了完整打包“历史遗留的二维形状”！
痛点：普通标量无法传递二维信息在基础的一维 DP（如打家劫舍）中，状态是一个“标量”（例如“前i个房间偷了多少钱”）。但在棋盘放国王时，当你站在第i行准备放棋子，你面临的不是一个点，而是一条长达N个格子的战线。如果你只记录“上一行放了 3 个国王”，这毫无意义——你不知道这 3 个国王是挤在左边还是散布在两边，也就根本无法判断当前行的哪些格子是安全的。一整行的 0 和 1 构成的“二维形状”，是约束下一行的最小信息单元，绝对不能被拆散。
截面理论：为什么刚好压缩“一行”？国王的攻击半径是 1，只能打到上下左右和对角线。这意味着，第i行的安危，仅受第i-1行的直接威胁。这就好比拿刀切断棋盘，为了保持“无后效性”，你的刀刃（状态记录）必须足够厚，厚到能挡住所有的攻击判定。因为攻击只能穿透 1 行，我们把“1 整行”作为一个切面打包，就完美切断了前后的联系。（思考题：如果是放“马”走日字，会攻击到前两行，这时候你的截面该有多厚？答案是必须同时压缩连续的两行！）
状压的本质：降维欺骗 DP 框架不能用数组套数组（
f[i][ array ]），那我们就把1010这样的阵型，直接看作一个十进制的整数10。状压 DP 的本质，就是把一整个复杂局面（一行的 01 排列）打包成一个二进制数，强行降维成一个普通数字，塞进 DP 数组的维度里。
三、 算法设计与样例推演
1. 状态定义
设f[i][j][o]表示：
i：当前推导到第i行。
j：截止到目前（前i行）总共放置了j个国王。
o：第i行采用的阵型是第o个合法状态（由于合法状态不多，我们对其进行了离散化编号）。
2. 状态转移方程
f[i][j][o] =
代表当前阵型o消耗了几个国王。
b代表上一行所有不与当前阵型o冲突的合法阵型编号。
3. 极简样例推演
假设N=3, K=2。
预处理：单行不冲突的合法状态有 000(需0人), 001(1人), 010(1人), 100(1人), 101(2人) 等。
推导第 1 行：若采用101（用2人），则回头去查第 0 行用 0 人的账本，方案数f[1][2][101] += f[0][0][0]，即为 1。
推导第 2 行：若第 2 行想采用010（用1人），它会试图继承第 1 行用 1 人的方案。但由于010和101在对角线上冲突，位运算拦截生效，010无法继承101留下的方案。
四、 时空复杂度分析
空间复杂度： 状态维数为f[15][110][150]。由于N=10时，单行没有相邻 1 的合法状态仅有 144 个（隐含斐波那契数列规律），所以第三维开到 150 足矣。 总空间为
bytes（
long long），远低于题目要求的
限制，空间极其充裕。
时间复杂度： 外层N循环 10 次，K循环 100 次，内部两层有效状态循环
。 总计算次数约为
次。在 C++ 每秒10^8次基本运算的红线内，毫无压力。复杂度严格为
，其中M为离散化后的合法状态数。
五、 坑点与易错总结
防爆
long long：方案总数随着N增大呈指数级上升，DP 数组和最终的ans必须使用long long，否则在累加过程中极易爆int变成负数。算术地基
f[0][0][0] = 1：第 0 行放置 0 个国王是一种绝对成立的底层推导基石。如果没有这块地基点燃火种，后续所有的+=皆为 0。位运算优先级陷阱：在 C++ 中，按位与
&的优先级低于逻辑等==。写成i & i << 1 == 0是极其致命的，会被解析成i & (i << 1 == 0)。必须严格加括号写成(i & (i << 1)) == 0！
六、 代码进阶与优化剖析（核心教学点）
虽然基础的四重循环已经足以 AC，但为了应对 CSP-S 考场上可能出现的“毒瘤”卡常数据，代码仍有两个高阶优化空间：
1. 常数优化：用“邻接表”预处理合法转移对（大幅降常数）
痛点：在最内层的两重
循环中，每次都要做一长串位运算冲突检测。其实不管在第几行，状态A能否接在状态B后面是永恒不变的。
进阶：在开头预处理阶段，开一个
vector<int> valid_moves[150]，提前穷举并记录所有不冲突的(A, B)状态对。最内层转移时直接写成for(int b : valid_moves[o])，彻底砍掉废循环和多余判断。
2. 位运算奇技淫巧：__builtin_popcount替代循环数 1
痛点：求当前状态需要几个国王时，用了
for循环遍历每一位。进阶：C++ 提供了编译器内置函数
__builtin_popcount(x)，它能直接在硬件指令级别 O(1)速度返回整型数字在二进制下 1 的个数，代码更精简，运行更极速。
七、 完整代码
//1.看数据范围 n最大不超过10 //所以棋盘最大不会超过100个格子 如果直接打暴力 //每个格子有放与不放两种情况 2^100肯定超时 //2.所以我们要用dp 但这道题的状态表示每个格子是否放了国王 //不太好表示 同时每一行放了几个国王毫无意义 并不能帮助解题 //但国王的攻击范围只影响相邻行 我们就可以把一整行的状态都作为一个维度 //我们发现一整行的01阵型作为一个整体传递下去 //只能选用按行转移的状压dp 将一整行的摆放情况 压缩成一个n位二进制数 //3.状态定义：f[i][j][o] //代表当前判断到第i行 截止到目前总共放置了j个国王 且当前行的阵型下标为o //o是合法状态数组a的下标 a[o].id才是真实的二进制状态 //比如二进制1010代表当前行第2和第4列放置了国王 //4.状态转移：f[i][j][o]=Σf[i-1][j-a[o].cnt][b] //o为当前行阵型下标 //b为上一行阵型下标 a[o].cnt为当前行摆了这个阵型要花费的国王数 //5.接下来我们观察f的第三维，因为n最大为10，2^10-1=1024 //第三维最大可以为1024 但是我们真的需要开这么大空间吗 //我们可以观察到10位二进制数的所有组合中 有大量相邻有1的组合 //但国王不能相邻，所以我们把有相邻1的不合法状态全部删除 //所以我们把相邻有1的全部排除掉 最多也就只能有144种可能 //所以我们第三维开到150足够了 然后对所有可能进行离散化 用idx进行编号 #include <iostream> using namespace std; int n,k; long long f[15][110][150]; struct node{ int id;//记录合法情况二进制数本身（真实的01阵型） //代表当前整数二进制表示下（当前阵型）包含的国王数 //当前整数二进制里1的个数 int cnt; }a[150]; int idx;//总合法情况数（0-base) int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; //对单行所有可能的阵型进行预处理 //一行最多n个格子 所以状态上限是(1<<n)-1 for(int i=0;i<(1<<n);i++){ //如果i自己和自己左移一位没有交集 说明不存在相邻的国王 if((i&(i<<1))==0){ a[idx].id=i; //统计当前合法阵型里用了几个国王（查i二进制位有几个1） //【优化批注】：此处可直接改写为 //a[idx].cnt= __builtin_popcount(i); 实现 O(1) 统计 for(int j=0;j<n;j++){ if((i&(1<<j))!=0) a[idx].cnt++; } idx++;//当前状态信息全部录入 合法情况数+1 } } //初始化 //第0行 放置0个国王 采用第0个合法状态（即全0状态）只有一种摆法 //因为上面的预处理是从i=0开始的 所以a[0].id必然是全0状态 f[0][0][0]=1; //最外层遍历行数 从第一行开始往下 for(int i=1;i<=n;i++){ //遍历截止到目前这一行 一共打算放置j个国王 for(int j=0;j<=k;j++){ //枚举当前行（i)采用的阵型下标o for(int o=0;o<idx;o++){ int s2=a[o].id;//s2为当前行真实的二进制阵型 int cnt2=a[o].cnt;//cnt2为当前阵型所需要使用的国王数 //如果当前行的阵型所需要使用的国王数 //比截止目前总共可以使用的国王总数j都多 就直接跳过 if(cnt2>j) continue; //如果当前行所需使用的国王数比国王总数少 就可以继续 else{ //枚举当前行的上一行的阵型(b) //【优化批注】：若预先统计了不冲突关系， //此处可降维为 for(int b : valid_moves[o]) for(int b=0;b<idx;b++){ //s1为当前行上一行的具体二进制表示 int s1=a[b].id; //接下来要判断上一行s1和当前行s2是否有冲突 //(s2&s1)==0 确保当前行没有国王在上一行国王的正下方 //(s2&(s1<<1))==0 确保当前行没有国王在上一行国王的左下方 //((s2<<1)&s1)==0 确保当前行没有国王在上一行国王的右下方 if(((s2&s1)==0)&&((s2&(s1<<1))==0)&&(((s2<<1)&s1)==0)) //如果不冲突 就把上一行的方案数累加过来 f[i][j][o]+=f[i-1][j-cnt2][b]; } } } } } long long ans=0; //目标n行 恰好用掉k个国王 //所以去表里把第n行 人数为k时 所有合法的阵型方案数全加起来 //就是最终答案 for(int b=0;b<idx;b++){ ans+=f[n][k][b]; } cout<<ans; return 0; }
