一道超级简单的状压DP题所以说状压是个好东西

看数据范围，同时我们发现一个格子要么放国王or不放，因此可以用二进制数来表示某一行的国王放置信息

于是我们马上想到用\(f_{i,j}\)表示放了前\(i\)行，其中第\(i\)行的国王摆放情况为\(j\)时的方案数

那么转移就很显然了，每次我们枚举本行的国王信息以及上一行的放置位置，然后判断是否合法即可。

具体的操作其实就是\(<<,>>\)之后\(\&\)一下即可，这个自己看

那么这样时限可能有点紧，我们还可以预处理一下每一行的合法情况，然后每次只枚举这些合法情况

当然还有些dalao说可以两行一起处理，这样会更快

反正我这么菜肯定不会，其他的看CODE吧

// luogu-judger-enable-o2

#include<cstdio>

using namespace std;

const int N=10;

long long f[N][(1<<N)+5][N*N],ans;

int n,m,tot,t[(1<<N)+5];

bool c[(1<<N)+5];

inline bool check(int x)

{

    int flag=0;

    while (x)

    {

        if ((x&1)&flag) return 0;

        flag=x&1; x>>=1;

    } return 1;

}

inline int calc(int x)

{

    int res=0; while (x) res+=x&1,x>>=1; return res;

}

inline bool judge(int x,int y)

{

    return !(x&y||x&(y<<1)||(x<<1)&y);

}

int main()

{

    scanf("%d%d",&n,&m); register int i,j,k,s; tot=(1<<n)-1;

    for (i=0;i<=tot;++i)

    c[i]=check(i),t[i]=calc(i);

    for (i=0;i<=tot;++i)

    if (c[i]) f[1][i][t[i]]=1;

    for (i=2;i<=n;++i)

    for (j=0;j<=tot;++j)

    if (c[j]) for (k=0;k<=tot;++k)

    if (c[k]&&judge(j,k))

    for (s=m;s>=t[j];--s) f[i][j][s]+=f[i-1][k][s-t[j]];

    for (i=0;i<=tot;++i)

    ans+=f[n][i][m];

    return printf("%lld",ans),0;

}