# [solution] Chinese chess - put on the horse

Chinese chess - put on the horse

### General idea of the topic

Given a \ (n\times m \) chessboard, place horses on the chessboard and ask how many swing methods can prevent horses from attacking each other. The horse is the horse of Chinese chess. It can be blocked from the attack route, as shown in the title stem.

### Problem solving

When you see the data range, the first thing you think of is shape pressure. We found that the states involved in the horse are actually the first two columns, so we need to save the states of the first two columns.

Then we have a natural state design: \ (f[i][j][k] \) represents row \ (I \), and the states of the first two columns are the scheme number of the current row of \ (j,k \). Obviously, the transfer order can be transferred directly from top to top.

Let's analyze this \ (dp. \) from initialization

For the first line, it is obvious that only \ (f[1][0][0]=2^m, \) can be directly assigned.

For the second row, consider all the possibilities of directly violent processing of two adjacent rows, complexity \ (O(4^m), \) as for the specific processing details, since there are only two rows, the only thing to judge is whether the lower row can attack the upper row and whether the upper row can attack the lower row.

If you can attack, you need to meet that it is not blocked and there is a horse in the attack position. Simple bit operation can be calculated.

bool check(int x,int y){
for(int i=2;i<m;++i){
if(!(y>>i&1))continue;
int v=(y>>(i-1))&1;
if(v)continue;
if(x>>(i-2)&1)return false;
}
for(int i=2;i<m;++i){
if(!(x>>i&1))continue;
int v=(x>>(i-1)&1);
if(v)continue;
if(y>>(i-2)&1)return false;
}
for(int i=0;i<m-2;++i){
if(!(y>>i&1))continue;
int v=(y>>(i+1)&1);
if(v)continue;
if(x>>(i+2)&1)return false;
}
for(int i=0;i<m-2;++i){
if(!(x>>i&1))continue;
int v=(x>>(i+1)&1);
if(v)continue;
if(y>>(i+2)&1)return false;
}
return true;
}


Continue to think. So far, we have solved the problem of initialization. Consider how to \ (dp: \)

An obvious idea is to enumerate the lines, enumerate the status of the previous line, uplink and uplink, and then consider what to fill in the current line.

Since the number of items that can be filled in the current line will only be affected by the first two lines, this part can also be preprocessed directly, with complexity \ (O(8^m). \)

Next, we encounter a small problem. We don't know how to inherit the previous state. Since the state we designed does not include the specific state of the current line, we cannot directly obtain the number of schemes when the states of the first two lines are \ (j,k \) respectively.

However, we can directly enumerate the upstream and upstream states. We found that if this state can meet the states of the last two lines of the current enumeration, the information inherited from the previous line is the same. In other words, we can directly use this information to get rid of the number of schemes that can be filled in the previous line in the current situation, and then we can get the number of filling schemes in the previous line in the fixed state.

As for how to judge the legitimacy of three lines of horses, first judge the adjacent horses. Then the horses separated by one line are also easy to judge. There are only two situations: either the upper horse goes to the lower part to attack, or the lower horse goes to the upper part to attack. Just judge like two horses.

bool check(int x,int y,int z){
for(int i=0;i<m;++i){
if(y>>i&1)continue;
if(!(z>>i&1))continue;
if(i&&(x>>(i-1)&1))return false;
if(i<m-1&&(x>>(i+1)&1))return false;
}
for(int i=0;i<m;++i){
if(y>>i&1)continue;
if(!(x>>i&1))continue;
if(i&&(z>>(i-1)&1))return false;
if(i<m-1&&(z>>(i+1)&1))return false;
}
return true;
}


Then, this division can directly preprocess the inverse element in the modular sense, and the complexity \ (O(2^m\log \bmod) \)

The total \ (dp \) complexity is \ (O(n\times 8^m). \) the space is found after writing.

Since rows have little effect on our state, we can scroll the array directly.

Complexity \ (O(n\times 2^8). \)

#include<bits/stdc++.h>
using namespace std;
typedef double db;
//#define int long long
const int mod=1e9+7;
const db eps=1e-14;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline db Max(db x,db y){return x-y>eps?x:y;}
inline db Min(db x,db y){return x-y<eps?x:y;}
inline int Add(int x,int y,int M=mod){return (x+y)%M;}
inline int Mul(int x,int y,int M=mod){return 1ll*x*y%M;}
inline int Dec(int x,int y,int M=mod){return (x-y+M)%M;}
inline int Abs(int x){return x<0?-x:x;}
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline int qpow(int x,int y){
int res=1;
while(y){
if(y&1)res=Mul(res,x);
x=Mul(x,x);y>>=1;
}
return res;
}
typedef pair<int,int> pr;
#define fi first
#define se second
#define mk make_pair
#define pb emplace_back
#define poly vector<int>
namespace Refined_heart{
int f[2][1<<6][1<<6],n,m,val[1<<6][1<<6],ival[1<<6][1<<6];
bool check(int x,int y){
for(int i=2;i<m;++i){
if(!(y>>i&1))continue;
int v=(y>>(i-1))&1;
if(v)continue;
if(x>>(i-2)&1)return false;
}
for(int i=2;i<m;++i){
if(!(x>>i&1))continue;
int v=(x>>(i-1)&1);
if(v)continue;
if(y>>(i-2)&1)return false;
}
for(int i=0;i<m-2;++i){
if(!(y>>i&1))continue;
int v=(y>>(i+1)&1);
if(v)continue;
if(x>>(i+2)&1)return false;
}
for(int i=0;i<m-2;++i){
if(!(x>>i&1))continue;
int v=(x>>(i+1)&1);
if(v)continue;
if(y>>(i+2)&1)return false;
}
return true;
}
int calc(int state){
int res=0;
for(int i=0;i<(1<<m);++i)res+=check(i,state);
return res;
}
bool check(int x,int y,int z){
for(int i=0;i<m;++i){
if(y>>i&1)continue;
if(!(z>>i&1))continue;
if(i&&(x>>(i-1)&1))return false;
if(i<m-1&&(x>>(i+1)&1))return false;
}
for(int i=0;i<m;++i){
if(y>>i&1)continue;
if(!(x>>i&1))continue;
if(i&&(z>>(i-1)&1))return false;
if(i<m-1&&(z>>(i+1)&1))return false;
}
return true;
}
void treat(){
for(int i=0;i<(1<<m);++i)
for(int j=0;j<(1<<m);++j){
if(!check(i,j))continue;
for(int k=0;k<(1<<m);++k){
if(!check(j,k))continue;
val[i][j]+=check(i,j,k);
}
}
for(int i=0;i<(1<<m);++i)
for(int j=0;j<(1<<m);++j)
ival[i][j]=qpow(val[i][j],mod-2);
}
void MAIN(){
f[1][0][0]=1<<m;
for(int i=0;i<(1<<m);++i)f[0][i][0]=calc(i);
treat();
for(int i=3;i<=n;++i){
int pos=i&1;
memset(f[pos],0,sizeof f[pos]);
for(int j=0;j<(1<<m);++j){
for(int k=0;k<(1<<m);++k){
if(!check(k,j))continue;
int s=0;
for(int l=0;l<(1<<m);++l){
if(!check(l,k))continue;
if(!check(l,k,j))continue;
}
}
}
}
int ans=0;
for(int i=0;i<(1<<m);++i)
for(int j=0;j<(1<<m);++j)
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}