蓝桥杯2021年第十二届真题第二场-国际象棋

题目

题目描述

众所周知，“八皇后” 问题是求解在国际象棋棋盘上摆放 8 8 8 个皇后，使得两两之间互不攻击的方案数。

已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹未尽。

作为一个国际象棋迷，他想研究在 N × M N × M N×M 的棋盘上，摆放 K K K 个马，使得两两之间互不攻击有多少种摆放方案。

由于方案数可能很大，只需计算答案除以 1000000007 1000000007 1000000007 (即 1 0 9 + 7 10^9+7 109+7) 的余数。

如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字，位于 ( x , y ) ( x , y ) (x,y) 格的马（第 x x x 行第 y y y 列）可以攻击 ( x + 1 , y + 2 ) ( x + 1 , y + 2 ) (x+1,y+2) 、 ( x + 1 , y − 2 ) ( x + 1 , y − 2 ) (x+1,y−2) 、 ( x − 1 , y + 2 ) ( x − 1 , y + 2 ) (x−1,y+2) 、 ( x − 1 , y − 2 ) ( x − 1 , y − 2 ) (x−1,y−2) 、 ( x + 2 , y + 1 ) ( x + 2 , y + 1 ) (x+2,y+1) 、 ( x + 2 , y − 1 ) ( x + 2 , y − 1 ) (x+2,y−1) 、 ( x − 2 , y + 1 ) ( x − 2 , y + 1 ) (x−2,y+1) 和 ( x − 2 , y − 1 ) ( x − 2 , y − 1 ) (x−2,y−1)共 8 个格子。

输入格式 输入一行包含三个正整数 N N N , M M M , K K K，分别表示棋盘的行数、列数和马的个数。

输出格式 输出一个整数，表示摆放的方案数除以 1000000007 1000000007 1000000007 (即 1 0 9 + 7 10^9+7 109+7) 的余数。

输入样例1 1 2 1

输出样例1 2

输入样例2 4 4 3

输出样例2 276

输入样例3 3 20 12

输出样例3 914051446

数据范围 对于 5 % 5\% 5% 的评测用例，$K = $ 对于另外 10 % 10\% 10% 的评测用例， K = 2 K = 2 K=2 对于另外 10 % 10\% 10% 的评测用例， N = 1 N = 1 N=1 对于另外 20 % 20\% 20% 的评测用例， N , M ≤ 6 N , M ≤ 6 N,M≤6 ， K ≤ 5 K ≤ 5 K≤5 对于另外 25 % 25\% 25% 的评测用例， N ≤ 3 N ≤ 3 N≤3 ， M ≤ 20 M ≤ 20 M≤20 ， K ≤ 12 K ≤ 12 K≤12 对于所有评测用例， 1 ≤ N ≤ 6 1 ≤ N ≤ 6 1≤N≤6 ， 1 ≤ M ≤ 100 1 ≤ M ≤ 100 1≤M≤100 ， 1 ≤ K ≤ 20 1 ≤ K ≤ 20 1≤K≤20

题解

f[i][k][b][a]：在前 i i i 行放置了 k k k 个马，且第 i − 1 i − 1 i−1 行的状态为 b b b，第 i i i 行的状态为 a a a 的方案数。

• 由于我们要用一个二进制数表示每一行的状态，而此题的 m = 100 m = 100 m=100，但 2 100 2^{100} 2100 是无法接受的
• 因此我们可以换个思路，将棋盘看成是 M × N M × N M×N 的，这样每行最多仅有 2 6 2^6 26 个二进制状态

如何判断冲突：

• 假设第 i i i 行的状态为 a a a，第 i − 1 i − 1 i−1 行的状态为 b b b，第 i − 2 i − 2 i−2 行的状态为 c c c； 若想在第 i i i 行的第 j j j 列放一匹马，则：
• 第 i − 1 i − 1 i−1 行的第 j − 2 j − 2 j−2 、 j + 2 j + 2 j+2 列不能有马，即 a & (b > 2) == 0
• 第 i − 2 i − 2 i−2 行的第 j − 1 j − 1 j−1 、 j + 1 j + 1 j+1 列不能有马，即 a & (c > 1) == 0
• 同时第 i − 1 i − 1 i−1 行与第 i − 2 i − 2 i−2 行也不能有冲突，即 b & (c > 2) == 0

代码

#include
using namespace std;
const int MOD = 1e9+7;

int n, m, K, ans, dp[110][21][100][100];

int count (int x) {
	int res = 0;
	while (x) {
		res += (x & 1);
		x >>= 1;
	}
	return res;
}

int main()
{
	cin >> n >> m >> K;
	
	dp[0][0][0][0] = 1;
	
	for (int i = 1;i