题目
题目描述
众所周知，“八皇后” 问题是求解在国际象棋棋盘上摆放
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 且 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 且 a & (c >> 1) == 0
- 同时第
i
−
1
i − 1
i−1 行与第
i
−
2
i − 2
i−2 行也不能有冲突，即
b & (c << 2) == 0 且 b & (c >> 2) == 0
代码
#include<bits/stdc++.h>
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 <= m;i ++)
for (int k = 0;k <= K;k ++)
for (int a = 0;a < 1 << n;a ++) { // 第i行的状态
for (int b = 0;b < 1 << n;b ++) { // 第i-1行的状态
if ((a & (b << 2)) || (a & (b >> 2))) continue;
for (int c = 0;c < 1 << n;c ++) { // 第i-2行的状态
if ((a & (c << 1)) || (a & (c >> 1))) continue;
if ((b & (c << 2)) || (b & (c >> 2))) continue;
int t = count (a);
if (k >= t)
dp[i][k][b][a] = (dp[i][k][b][a] + dp[i-1][k - t][c][b]) % MOD;
}
}
}
for (int a = 0;a < 1 << n;a ++)
for (int b = 0;b < 1 << n;b ++)
ans = (ans + dp[m][K][b][a]) % MOD;
cout << ans << endl;
return 0;
}
存在一个问题，不用考虑蹩马腿的情况吗？
