https://www.luogu.org/problemnew/show/P1896

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

输入格式：

 

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

 

输出格式：

 

所得的方案数

 

思路：设f(i,j,k)：前i行，第i行压位后为state[]第j个元素，目前已经放了k个国王，对应的方案数。

同一行的攻击（等价于任意两点不相邻）开始时就预处理好放在state[]中

上下的攻击分别判断a&b，a<<1&b,a&b<<1。

转移是比较裸的。

要开long long

#include<bits/stdc++.h>
using namespace std;
#define mod 100000000

int n,k;
int state[1<<10],tot;
long long f[10][1<<10][100];//第二维是在state[]中的下标，而非实际二进制 

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>k;
	for(int i=0;i<(1<<n);i++)if(!(i&(i<<1)))state[tot++]=i;
	
	for(int i=0;i<tot;i++)
	{
		int s=state[i],cnt=0;
		for(int j=0;j<n;j++)if((1<<j)&s)cnt++;
		f[0][i][cnt]++;
	}
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<tot;j++)
		{
			for(int s=0;s<tot;s++)
			{
				if((state[s]&state[j])==0&&(state[s]&(state[j]<<1))==0&&((state[s]<<1)&state[j])==0)
				{
					int cnt=0;
					for(int l=0;l<n;l++)if((1<<l)&state[j])cnt++;
					for(int p=cnt;p<=k;p++)f[i][j][p]+=f[i-1][s][p-cnt];
				}
			}
		}
	}
	long long ans=0;
	for(int j=0;j<tot;j++)ans+=f[n-1][j][k];
	cout<<ans<<endl;
	exit(0);
}