状压DP是利用计算机二进制的性质来描述状态的一种DP方式，
通过将状态压缩为整数来达到优化转移的目的。
很多棋盘问题运用到状压DP.

/* https://www.luogu.com.cn/problem/P1896 */

/*
    状态方程:
    当前行(i)的状态为j,上一行(i-1)的状态为x
    f[i][j][k]=∑f[i-1][x][k - king[j]]
*/
#include
using namespace std;

const int MAXN = 100;
// 可用状态的十进制
int state[MAXN];
// 可用状态下的国王数，即state[i]的二进制中1的个数
int king[MAXN];
// f[i][j][k]: 当第i行状态j(状态值为state[j])时，已经放置了k个国王的总方案数
long f[10][MAXN][26];

int N, K, total = 0;
//  统计n的二进制中1的个数
unsigned int statistic1(unsigned int n)
{
    unsigned int cnt = 0 ;
    for (cnt = 0; n; ++cnt)
    {
        n &= (n - 1); // clean the lowest order 1
    }
    return cnt ;
}

void init()
{
    int cnt = 0;
    for (int i = 0; i <(1<     {
        // 如果存在2个国王左右相邻
        if (i & (i<<1))
            continue;
        state[++total] = i;
        king[total] = statistic1(i);
    }
}

bool compatible(int i, int j) 
{
    // 上下有重复的king
    if (state[i] & state[j])
        return false;
    // 左上右下有重复king
    if ((state[i] << 1) & state[j])
        return false;
    // 右上左下有重复king
    if (state[i] & (state[j] << 1))
        return false;

  return true;
}

int main()
{
    cin >> N >> K;
    init();

    int i, j, k, x;
    for (j = 1; j <= total; ++j)
        f[1][j][king[j]] = 1;

    for (i = 2; i <= N; ++i)
        for (j = 1; j <= total; ++j) // 第i行的状态为j
            for (x = 1; x <= total; ++x) // 第i-1行的状态为x
                if (compatible(j, x))
                {
                    for (k = king[j]; k <= K; ++k)
                        f[i][j][k] += f[i - 1][x][k - king[j]];
                }

    long long ans = 0;
    for (j = 1; j <= total; ++j)
        ans += f[N][j][K];

    cout << ans << endl;

    return 0;
}