小国王

在 n×n 的棋盘上放 k 个国王,国王可攻击相邻的 8 个格子,求使它们无法互相攻击的方案总数。

输入格式

共一行,包含两个整数 n 和 k。

输出格式

共一行,表示方案总数,若不能够放置则输出0。

数据范围

1≤n≤10
0≤k≤n2

输入样例:

3 2

输出样例:

16

#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const LL N=13,M=1<<10;
LL f[N][110][M];
int cnt[M];
LL n,k;
vector<int> v;
vector<int> state[M];
bool check(LL st)
{
    for(int i=0;i<n-1;++i)
    {
        if((st>>i&1)&&(st>>(i+1)&1)) return false;
    }
    return true;
}
int count(int x)
{
    int res=0;
    for(int i=0;i<n;++i) if((x>>i)&1) res++;
    return res;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<1<<n;++i)
    {
        if(check(i))
        {
            v.push_back(i);
            cnt[i]=count(i);
        }
    }
    
    for(int i=0;i<v.size();++i)
    {
        for(int j=0;j<v.size();++j)
        {
            int a=v[i],b=v[j];
            if((a&b)==0&&check(a|b))
            {
                state[a].push_back(b);
            }
        }
    }
    f[0][0][0]=1;
    for(int i=1;i<=n+1;++i)
    {
        for(int j=0;j<=k;++j)
        {
            for(int a:v)
            {
                for(int b:state[a])
                {
                    int c=cnt[a];
                    if(j>=c)
                    {
                        f[i][j][a]+=f[i-1][j-c][b];
                    }
                }
            }
        }
    }
    
    cout<<f[n+1][k][0]<<endl;
    return 0;
}