, C/C++ Programming

Question 1 / 1
You have an N x N chessboard and you wish to place N kings on it. Each row and column should contain exactly one king, and no two kings should attack each other (two kings attack each other if they are present in squares which share a corner).

The kings in the first K rows of the board have already been placed. You are given the positions of these kings as an array pos[ ]. pos[i] is the column in which the king in the ith row has already been placed. All indices are 0-indexed. In how many ways can the remaining kings be placed?

Input:
The first line contains the number of test cases T. T test cases follow. Each test case contains N and K on the first line, followed by a line having K integers, denoting the array pos[ ] as described above.

Output:
Output the number of ways to place kings in the remaining rows satisfying the above conditions. Output all numbers modulo 1000000007.

Constraints:
1 <= T <= 20
1 <= N <= 16
0 <= K <= N
0 <= pos_i < N
The kings specified in the input will be in different columns and not attack each other.

Sample Input:
5
4 1
2
3 0

5 2
1 3
4 4
1 3 0 2
6 1
2

Sample Output:
1
0
2
1
18

Explanation:
For the first example, there is a king already placed at row 0 and column 2. The king in the second row must belong to column 0. The king in the third row must belong to column 3, and the last king must beong to column 1. Thus there is only 1 valid placement.

For the second example, there is no valid placement.
Posted Date: 9/9/2012 3:44:09 PM | Location : United States







Related Discussions:- , Assignment Help, Ask Question on , Get Answer, Expert's Help, Discussions

Write discussion on
Your posts are moderated
Related Questions
The car’s measurements are illustrated, using two arrays. Array 1 = {L, R, L, R, R, L, R, R, L, R, R, L, R, L, L, R, Z}

Bit-wise Operators Some applications require operations to be done on dissimilar bits of a byte separately. Bit-wise operators offer a facility to do just that. There are vario

A: Mostly can be overloaded. The only C operators which can't be are. and?: (and sizeof, that is technically an operator). C++ adds a few of its own operators, mostly which can be

write a program to accept ten numbers and display the total

Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b

assume that the first integer read with cin specifies the number of values remaining to be entered. that program should read only one value each time cin is executed .a typical inp

A palindrome is a string that reads the same from both the ends. Given a string S convert it to a palindrome by doing character replacement. Your task is to convert S to palindrome

C Program for SORTING # include stdio.h> void main() {           char a;           int *p;           int i,j,temp;           clrscr();           p=&i;

Given a bool variable isReadable write some statements that assign true to isReadable if the file "topsecret" exists and can be read by the program and assigns false to isR

#write a program that counts the number of occurances of the string in the n-th padovan string p(n)