2014
02-27

# N Knight

Today, chess is one of the world’s most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.

Chess is played on a square board of eight rows and eight columns and denoted with letters a to h of squares. The colors of the sixty-four squares alternate and are referred to as "light squares" and "dark squares". The chessboard is placed with a light square at the right hand end of the rank nearest to each player, and the pieces are set out as shown in the diagram, with each queen on its own color.

The pieces are divided, by convention, into white and black sets. The players are referred to as "White" and "Black", and each begins the game with sixteen pieces of the specified color. These consist of one king, one queen, two rooks, two bishops, two knights and eight pawns.

Now we have another way to play with the chessboard. Give you a N*N chessboard, and ask you to place N knights on it. But the knights can’t attack each other (one knight can attack other chessman in the same row or in the column). And what’s more, no more than M knights are permissible to put on the reverse diagonal (the black grids as following picture). Now ask you how many different ways you can place this N Knight.

Input contains multiple cases each presented on a separate line. Each line contains two integer numbers N,M(1<=N<=1000,0<=M<=N).

Input contains multiple cases each presented on a separate line. Each line contains two integer numbers N,M(1<=N<=1000,0<=M<=N).

1 1

1

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮