DP Finite Automata with Compression: Little King

In a n × n board, there are k Kings, kings can attack 8 surrounding neighbors, find the total number of solutions that make them unable to attack each other.

Input format

A line containing two integers n and k.

Output format

A total of one line, indicating the total number of solutions, if it cannot be placed, output 0.

data range

1 ≤ n ≤ 10 0 ≤ k ≤ n^2

Sample Input:

3 2


Sample Output:

16


Solution

dp[i][j][k]: i: current row, j: number of kings placed so far k:the placement of kings in row i We use an integer k to represent row i’s king’s placement in row i. A k-th bit 1 in k represent a king is planted in column k of row i.

 If we know i-th row is a, i-1 row is b, then the valid placement of kings are (a & b)==0 && check(a b).
• a&b == 0 means there’s no two kings on the same column in the two rows.
•  check(a b) means there’s no two diagnal kings in the two rows

dp[i][j][a] += dp[i-1][j-c][compatible_list[a][b]]