题目链接
题意分析
看数据范围就应该知道这是一道状压DP题了
一开始想的是设置dp[i][a] 表示第i行状态为a的方案数
那么状态转移的时候 (dp[i][a]=sum_{b=0}^{2^m-1}dp[i-1][b]) 并且满足a与b并不冲突
但是要注意的是影响第i行的不只有第i-1行 还有第i-2行
所以我想的就是(dp[i][a]=sum_{b=0}^{2^m-1}dp[i-1][b]-sum_{c=0}^{2^m-1}dp[i-2][c])
满足a与b不冲突 b与c不冲突 但是a，与c是冲突的
也就是减去曾经合法中如今不合法的方案
后来发现不行
因为我们不确定dp[i-1][b]中是否包含dp[i-2][c] 有可能会导致多减了
所以只能改变思路
只转移绝对合法的
设置dp[i][a][b] 表示第i行当前行状态为a,上一行状态为b的方案数
首先我们需要对第一行以及第二行初始化
然后进行状态转移就可以了
大体框架是如下的
for(int a=0;a<(1<<m);++a)//当前行
for(int b=0;b<(1<<m);++b)//上一行
{
if(a与b存在冲突) continue;
for(int c=0;c<(1<<m)；++c)
{
if(a与c存在冲突||b与c存在冲突) continue;
dp[i][a][b]+=dp[i-1][b][c];
}
}
接下来我们需要明白如何判断冲突
1.两行之间
一个第j列的棋子会被上一行攻击到
当且仅当第j-2列以及第j+2列存在马并且没有蹩马腿
所以我写了这么一个函数
bool check1(int nowat,int a,int b)
{
//nowat是当前判断棋子所在位置(0,1,...,m-1)
//b是当前行二进制状态
//a是上一行二进制状态
bool flag=1;
if(nowat>=2)//判断左边
{//没有攻击他的棋子或者攻击棋子蹩马腿 均不存在
//而且攻击是相互的
if(!(((1<<(nowat-2))&a)==0 || (((1<<(nowat-2))&a)!=0&&((1<<(nowat-1))&a)!=0))) flag=0;
if(!(((1<<(nowat-2))&a)==0 || (((1<<(nowat-2))&a)!=0&&((1<<(nowat-1))&b)!=0))) flag=0;
}
if(nowat<=(m-1-2))//判断右边
{
if(!(((1<<(nowat+2))&a)==0 || (((1<<(nowat+2))&a)!=0&&((1<<(nowat+1))&a)!=0))) flag=0;
if(!(((1<<(nowat+2))&a)==0 || (((1<<(nowat+2))&a)!=0&&((1<<(nowat+1))&b)!=0))) flag=0;
}
return flag;
}
2.三行之间
我们需要判断第j列的棋子是否会被上上行攻击到
当且仅当上上行第j-1列以及第j+1列没有棋子或者存在棋子被蹩马腿
所以我又写了这么一个函数
bool check2(int nowat,int a,int b,int c)
{
//c是上上行
//a是上一行
//b是当前行
bool flag=1;
if(nowat>=1)//判断左边
{
if(!(((1<<(nowat-1))&c)==0 || (((1<<(nowat-1))&c)!=0&&((1<<(nowat-1))&a)!=0))) flag=0;
if(!(((1<<(nowat-1))&c)==0 || (((1<<(nowat-1))&c)!=0&&((1<<nowat)&a)!=0))) flag=0;
}
if(nowat<=(m-1-1))//判断右边
{
if(!(((1<<(nowat+1))&c)==0 || (((1<<(nowat+1))&c)!=0&&((1<<(nowat+1))&a)!=0))) flag=0;
if(!(((1<<(nowat+1))&c)==0 || (((1<<(nowat+1))&c)!=0&&((1<<nowat)&a)!=0))) flag=0;
}
return flag;
}
好了之后 我们就可以开心的写出总代码了
注意 由于直接这么开数组 我们是会炸的题面说的也是明明白白了
由于这道题的转移上每一次都会只涉及到上一行 所以我们可以把第一维也就是行的那一维滚动一下
CODE:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define mod 1000000007
using namespace std;
int n,m;
long long dp[2][65][65],ans;
int ln[100];
bool check1(int nowat,int a,int b)
{
//b是当前行
//a是上一行
bool flag=1;
if(nowat>=2)
{
if(!(((1<<(nowat-2))&a)==0 || (((1<<(nowat-2))&a)!=0&&((1<<(nowat-1))&a)!=0))) flag=0;
if(!(((1<<(nowat-2))&a)==0 || (((1<<(nowat-2))&a)!=0&&((1<<(nowat-1))&b)!=0))) flag=0;
}
if(nowat<=(m-1-2))
{
if(!(((1<<(nowat+2))&a)==0 || (((1<<(nowat+2))&a)!=0&&((1<<(nowat+1))&a)!=0))) flag=0;
if(!(((1<<(nowat+2))&a)==0 || (((1<<(nowat+2))&a)!=0&&((1<<(nowat+1))&b)!=0))) flag=0;
}
return flag;
}
bool check2(int nowat,int a,int b,int c)
{
//c是上上行
//a是上一行
//b是当前行
bool flag=1;
if(nowat>=1)
{
if(!(((1<<(nowat-1))&c)==0 || (((1<<(nowat-1))&c)!=0&&((1<<(nowat-1))&a)!=0))) flag=0;
if(!(((1<<(nowat-1))&c)==0 || (((1<<(nowat-1))&c)!=0&&((1<<nowat)&a)!=0))) flag=0;
}
if(nowat<=(m-1-1))
{
if(!(((1<<(nowat+1))&c)==0 || (((1<<(nowat+1))&c)!=0&&((1<<(nowat+1))&a)!=0))) flag=0;
if(!(((1<<(nowat+1))&c)==0 || (((1<<(nowat+1))&c)!=0&&((1<<nowat)&a)!=0))) flag=0;
}
return flag;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<(1<<m);++i) dp[1][i][0]=1;
for(int i=0;i<=6;++i) ln[1<<i]=i;
for(int i=2,now=0;i<=n;++i,now^=1)
{
if(i==2)
{
for(int a=0;a<(1<<m);++a)//当前行
for(int b=0;b<(1<<m);++b)//上一行
{
bool flag=1;
for(int x=a;x>0;x-=x&-x)
{//由于本蒟蒻实在是太辣鸡了 所以不会用什么高级二进制法子 只能乖乖枚举了
int nowat=ln[x&-x];
if(!check1(nowat,b,a)) {flag=0;break;}
}
if(flag) dp[0][a][b]=(dp[0][a][b]+dp[1][b][0])%mod;
}
}
else
{
memset(dp[now],0,sizeof dp[now]);
for(int a=0;a<(1<<m);++a)//当前行
for(int b=0;b<(1<<m);++b)//上一行
{
bool flag1=1,flag2,flag3;
for(int x=a;x>0;x-=x&-x)
{//同上
int nowat=ln[x&-x];
if(!check1(nowat,b,a)) {flag1=0;break;}
}
if(flag1==0) continue;
for(int c=0;c<(1<<m);++c)//上上行
{
flag2=flag3=1;
for(int x=b;x>0;x-=x&-x)
{//同上
int nowat=ln[x&-x];
if(!check1(nowat,c,b)) {flag2=0;break;}
}
if(flag2==0) continue;
for(int x=a;x>0;x-=x&-x)
{
int nowat=ln[x&-x];
if(!check2(nowat,b,a,c)) {flag3=0;break;}
}
if(flag3==0) continue;
dp[now][a][b]=(dp[now][a][b]+dp[now^1][b][c])%mod;
}
}
}
}
for(int i=0;i<(1<<m);++i)
for(int j=0;j<(1<<m);++j)
ans=(ans+dp[n&1][i][j])%mod;
printf("%lld
",ans);
return 0;
}