国际象棋：模板棋盘状压。
摆上马：需要点思维的棋盘状压，相比上一道题加了“蹩马脚”的设定。
Easy_version ：国际象棋
概述一下此类棋盘问题的思路：
- 用二进制数表示出棋盘上某一行的状态。
- 用位运算预处理出合法的单行状态，以及需要用到的一些东西。
- 用位运算判断前一行或者前几行能否转移过来。
- 转移前一行或者前几行的兼容类。
基础位运算
判断两边是否有：i&(i>>1) 和 i&(i<<1) 。
判断 \(i\) 是否包含在合法状态 \(j\) 里： (i&j)==i 。
对于本题
记录下两行的状态，定义 \(dp[i][j][k][l]\) 表示第 \(i\) 行时，第 \(i\)行状态为 \(j\) ，第 \(i-1\) 行状态为 \(k\) ，且目前摆了 \(l\) 个马的方案数。
初始化 \(dp[0][0][0][0]=1\) 。
循环顺序是：
- 行数。
- 马的个数。
- 第 \(i\) 行状态。
- 第 \(i-1\) 行状态。
- 第 \(i-2\) 行状态。
注意由于只会用到前一行的状态，所以我们可以强行滚动数组优化，通过 \(\bmod 2\) 来解决。滚动数组每次必须先初始化为 \(0\) 。
时间复杂度 \(O(2^{3n}mk)\)，有点紧，常数不能太大。
为了不在最后统计一遍，太过麻烦，所以我们多加了两行，并强制这两行必须不能放马，这样就不用手工统计方案数了。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int n,m,k,tot[70];
const ll mod=1e9+7;
ll dp[2][70][70][25];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
for(int i=0;i<(1<<n);i++)
{
for(int j=0;j<n;j++)
{
tot[i]+=((i>>j)&1);
}
}
dp[0][0][0][0]=1;
for(int i=1;i<=m+2;i++)
{
for(int j=0;j<=k;j++)
{
for(int a=0;a<(1<<n);a++)
{
for(int b=0;b<(1<<n);b++)
{
dp[i&1][a][b][j]=0;
if(((a>>2)&b)||((a<<2)&b))continue;
for(int c=0;c<(1<<n);c++)
{
if(((a>>1)&c)||((a<<1)&c))continue;
if(tot[a]<=j)
{
dp[i&1][a][b][j]=(dp[i&1][a][b][j]+dp[(i&1)^1][b][c][j-tot[a]])%mod;
}
}
}
}
}
}
cout<<dp[(m+2)&1][0][0][k];
return 0;
}
Hard_version ：中国象棋 - 摆上马
相比上一道，这道必须考虑蹩马脚的情况，且不用记录马的个数。
这题难点便是在判断蹩马脚：
进阶位运算
筛选出本行左边是 \(0\) ，这一位是 \(1\) 的点： i&((~i)>>1) 。
筛选出本行右边是 \(0\) ，这一位是 \(1\) 的点： i&((~i)<<1) 。
考虑 \(i\) 和 \(i-1\) 行时
\(a\) 为第 \(i\) 行状态，\(b\) 为第 \(i-1\) 行状态，\(c\) 为第 \(i-2\) 行状态。
第 \(i\) 行左边没有蹩马脚，并且可以攻击到左上的马的情况：a&((~a)>>1)&(b>>2) 。
第 \(i\) 行右边没有蹩马脚，并且可以攻击到右上的马的情况：a&((~a)<<1)&(b<<2) 。
第 \(i-1\) 行左边没有蹩马脚，并且可以攻击到左下的马的情况：b&((~b)>>1)&(a>>2) 。
第 \(i-1\) 行右边没有蹩马脚，并且可以攻击到右下的马的情况：b&((~b)<<1)&(a<<2) 。
考虑 \(i\) 和 \(i-2\) 行时
第 \(i\) 行上边没有蹩马脚，并且可以攻击到左上的马的情况：a&(~b)&(c>>1) 。
第 \(i\) 行上边没有蹩马脚，并且可以攻击到右上的马的情况：a&(~b)&(c<<1) 。
第 \(i-2\) 行下边没有蹩马脚，并且可以攻击到左下的马的情况：c&(~b)&(a>>1) 。
第 \(i-2\) 行下边没有蹩马脚，并且可以攻击到右下的马的情况：c&(~b)&(a<<1) 。
时间复杂度 \(O(2^{3y}x)\) 。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int n,m;
const ll mod=1e9+7;
ll dp[2][70][70];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
dp[0][0][0]=1;
for(int i=1;i<=m+2;i++)
{
for(int a=0;a<(1<<n);a++)
{
for(int b=0;b<(1<<n);b++)
{
dp[i&1][a][b]=0;
if((a&((~a)>>1)&(b>>2))||((a&((~a)<<1)&(b<<2)))||(b&((~b)>>1)&(a>>2))||(b&((~b)<<1)&(a<<2)))continue;
for(int c=0;c<(1<<n);c++)
{
if(((~b)&a&(c>>1))||((~b)&a&(c<<1))||((~b)&c&(a<<1))||((~b)&c&(a>>1)))continue;
dp[i&1][a][b]=(dp[i&1][a][b]+dp[(i&1)^1][b][c])%mod;
}
}
}
}
cout<<dp[(m+2)&1][0][0];
return 0;
}