P1896 [SCOI2005] Non-aggression

Problem#

[SCOI2005] Non-Aggression#

Problem Description#

Place $K$ kings on an $N \times N$ chessboard such that they do not attack each other. How many arrangements are there? A king can attack one square in each of the eight directions: up, down, left, right, and the four diagonals, totaling $8$ squares.
For all data, $1 \le N \le 9$, $0 \le K \le N\times N$.

Solution#

Let f[i][j][k] represent the number of arrangements when reaching row i, having selected j kings so far, and the state of row i is k.

Then enumerate i,j,k and the state transition from the previous row.

Issues#

Do not forget to use long long.
The second dimension should be N * N!

Code#

#include<bits/stdc++.h>
#define int long long
using namespace std;

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}
const int N = 10;
int f[N][N * N][1 << 9];
int sum[1 << 9];
int n, k;

int getsum(int x)
{
	int ans = 0;
	while(x)
	{
		x &= (x - 1);
		ans++;
	}
	return ans;
}

signed main()
{
	for(int i = 0;i < (1 << 9);i++)
	{
		sum[i] = getsum(i);
	}
	n = read(), k = read();
	for(int s = 0;s < (1 << n);s++)
	{
		f[1][sum[s]][s] = 1;
	}

	for(int i = 2;i <= n;i++)
	{
		for(int j = 0;j <= k;j++)
		{
			for(int s = 0;s < (1 << n);s++)
			{
				if((s >> 1) & s || (s << 1) & s || sum[s] > j) continue;
				for(int fl = 0;fl < (1 << n);fl++)
				{
					if((fl >> 1) & fl || (fl << 1) & fl || (fl << 1) & s || fl & s || (fl >> 1) & s || sum[fl] + sum[s] > j) continue;
					f[i][j][s] += f[i - 1][j - sum[s]][fl];
				}
			}
		}

	}

	long long ans = 0;
	for(int s = 0; s < (1 << n);s++)
	{
		if((s >> 1) & s) continue;
			ans += f[n][k][s];
	}
	cout << ans;
	return 0;
}