uva-861 - Little Bishops

出處 ： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=802

Little Bishops

A bishop is a piece used in the game of chess which is played on a board of square grids. A bishop can only move diagonally from its current position and two bishops attack each other if one is on the path of the other. In the following figure, the dark squares represent the reachable locations for bishop B₁ form its current position. The figure also shows that the bishops B₁ and B₂ are in attacking positions whereas B₁ and B₃ are not. B₂ and B₃ are also in non-attacking positions.

Now, given two numbers n and k, your job is to determine the number of ways one can put k bishops on an n × n chessboard so that no two of them are in attacking positions.

Input

The input file may contain multiple test cases. Each test case occupies a single line in the input file and contains two integers n (1 ≤ n ≤ 8) and k (0 ≤ k ≤ n²).

A test case containing two zeros for n and k terminates the input and you won’t need to process this particular input.

Output

For each test case in the input print a line containing the total number of ways one can put the given number of bishops on a chessboard of the given size so that no two of them are in attacking positions. You may safely assume that this number will be less than 10¹⁵.

Sample Input

8 6

4 4

0 0

Sample Output

5599888

260

Problem setter: Rezaul Alam Chowdhury

"I think Garry Kasparov will like this problem very much!!!"

解題策略

先將棋盤交錯改成黑色與白色格子，黑色格子的象永遠不會與白色格子的象相剋

可以分開計算再相加，黑色與白色格子都可以轉45度來看，變成象棋的車

初始化

black[i][0]=1，對i=0到n，因為放零個象的個數為1種可能。

black[0][i]=0，對i=1到k，0x0的棋盤除了0個象為1之外其他都是0

可以利用dp得到以下關係

black[i][j]=black[i-1][j]+black[i-1][j-1]*(rowb[i]-(j-1));

前i行有j個象的可能個數等於 前i-1行有j個象(也就是第i行不放象)

加上 前i-1行有j-1個象可能個數乘以第i行的可擺放位置為(rowb[i]-(j-1))，rowb[i]為第i行個數

減去j-1個位置不能擺象，因為此時已經轉45度來看，不能放象

最後執行以下運算，sum為結果

sum+=black[n][i]*white[n-1][k-i]; 對i從0到k

黑色棋盤前n行擺i個象，白色棋盤前n-1行只能放k-i個象，兩者相乘