#include<bits/stdc++.h>
using namespace std;
const int N = 15, M = 110, K = 1 << 11;

typedef long long LL;

int n, m;

vector<int> head[K], state;
//head[i]存放下标为i的状态所能转移到的状态下标
//state 存放合法的状态

int cnt[K]; //存放每个状态下的国王个数

LL f[N][M][K];

bool check(int x) //判断是否有相邻的1
{
    return !(x & x >> 1);
}

int count(int x)
{
    int res = 0;
    for(int i = 0; i < n; i++)
        res += (x >> i & 1);

    return res; 
}

int main()
{
    cin >> n >> m;

    for(int i = 0; i < 1 << n; i++)
        if(check(i))
        {
            state.push_back(i);
            cnt[i] = count(i);
        }
    
    /*预处理2: 所有合法状态的转移过程*/
    for(int i = 0; i < state.size(); i++)
        for(int j = 0; j < state.size(); j++)
        {
            int a = state[i], b = state[j];
            if((a & b) == 0 && check(a | b))
            {
                head[i].push_back(j);
            }
        }

    f[0][0][0] = 1;
    for(int i = 1; i <= n + 1; i++)
        for(int j = 0; j <= m; j++) //枚举国王个数
            for(int a = 0;  a < state.size(); a ++) //枚举所有的合法状态
            {
                for(int b : head[a]) {//合法状态能转移的合法状态
                    int num = cnt[state[a]];
                    if(j >= num)
                    {
                        f[i][j][a] += f[i - 1][j - num][b];
                    }
                }
            }
    cout << f[n + 1][m][0];
    return 0;
}

/*
f[i][j][k]: 前i层棋盘,放置了j个国王,且第i层状态时k的方案
f[i][j][k] += f[i - 1][j - cnt[k]][pre_k];


sum(f[n][K][所有合法状态])
*/

0 条评论

目前还没有评论...