Расстановка слонов на шахматной доске

Требуется найти количество способов расставить K слонов на доске размером NxN.

Алгоритм

Решать задачу будем с помощью динамического программирования.

Пусть D[i][j] - количество способов расставить j слонов на диагоналях до i-ой включительно, причём только тех диагоналях, которые того же цвета, что и i-ая диагональ. Тогда i = 1..2N-1, j = 0..K.

Диагонали занумеруем следующим образом (пример для доски 5x5):

черные:     белые:
1 _ 5 _ 9   _ 2 _ 6 _
_ 5 _ 9 _   2 _ 6 _ 8
5 _ 9 _ 7   _ 6 _ 8 _ 
_ 9 _ 7 _   6 _ 8 _ 4
9 _ 7 _ 3   _ 8 _ 4 _

Т.е. нечётные номера соответствуют чёрным диагоналям, чётные - белым; диагонали нумеруем в порядке увеличения количества элементов в них.

При такой нумерации мы можем вычислить каждое D[i][], основываясь только на D[i-2][] (двойка вычитается, чтобы мы рассматривали диагональ того же цвета).

Итак, пусть текущий элемент динамики - D[i][j]. Имеем два перехода. Первый - D[i-2][j], т.е. ставим всех j слонов на предыдущие диагонали. Второй переход - если мы ставим одного слона на текущую диагональ, а остальных j-1 слонов - на предыдущие; заметим, что количество способов поставить слона на текущую диагональ равно количеству клеток в ней минус j-1, т.к. слоны, стоящие на предыдущих диагоналях, будут перекрывать часть направлений. Таким образом, имеем:

D[i][j] = D[i-2][j] + D[i-2][j-1] (cells(i) - j + 1)

где cells(i) - количество клеток, лежащих на i-ой диагонали. Например, cells можно вычислять так:

int cells (int i) {
	if (i & 1)
		return i / 4 * 2 + 1;
	else
		return (i - 1) / 4 * 2 + 2;
}

Осталось определить базу динамики, тут никаких сложностей нет: D[i][0] = 1, D[1][1] = 1.

Наконец, вычислив динамику, найти собственно ответ к задаче несложно. Перебираем количество i=0..K слонов, стоящих на чёрных диагоналях (номер последней чёрной диагонали - 2N-1), соответственно K-i слонов ставим на белые диагонали (номер последней белой диагонали - 2N-2), т.е. к ответу прибавляем величину D[2N-1][i] * D[2N-2][K-i].

Реализация

int n, k; // входные данные
if (k > 2*n-1) {
	cout << 0;
	return 0;
}

vector < vector<int> > d (n*2, vector<int> (k+2));
for (int i=0; i<n*2; ++i)
	d[i][0] = 1;
d[1][1] = 1;
for (int i=2; i<n*2; ++i)
	for (int j=1; j<=k; ++j)
		d[i][j] = d[i-2][j] + d[i-2][j-1] * (cells(i) - j + 1);

int ans = 0;
for (int i=0; i<=k; ++i)
	ans += d[n*2-1][i] * d[n*2-2][k-i];
cout << ans;