, C/C++ Programming

Assignment Help:
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.

Related Discussions:-

Describe "this" pointer?, It is a pointer accessible only in the member fun...

It is a pointer accessible only in the member functions of a struct, class or union type. It points to the object for which the member function is called. Static member functions d

Stack, Implement multiple stacks in a single dimensional array. Write algor...

Implement multiple stacks in a single dimensional array. Write algorithms for various stack operations for them.

Program Assignment #3, Programming Assignment #3: Vehicle Track Performance...

Programming Assignment #3: Vehicle Track Performance Tests Purpose: The purpose of this programming assignment is to give the student experience in using functions, arrays, and str

How do you access the values within an array, How do you access the values ...

How do you access the values within an array? - Arrays comprise a number of elements, which depends on the size you assigned it during variable declaration. - Every element

Program to input 2 date & produce a new date - c++ program, /*  THIS PROGRA...

/*  THIS PROGRAM IS TO ASK USER TO INPUT TWO DATE & PRODUCE A NEW DATE  */ #include #include struct date  {   int dd;   int yy;   int mm;  }; date add(date d1,date d2)    {

C program to convert time in 24 hour format to 12., Aim: To implement a pr...

Aim: To implement a program to convert time in 24 hour format to 12 hour format. Code:                       #include #include #include class time24 {

Example of array, In this lab, please complete a given program to perform t...

In this lab, please complete a given program to perform the following tasks: 1. Allocate a 10 by 5 2D byte array dynamically. The way of allocation must be consistent with pag

Explain the working of array with strings, Explain the working of Array wit...

Explain the working of Array with Strings? A string is defined in C language as an array of characters. A null character (‘\0') is automatically added to the end of the charact

Programming, pseudocode for gregorian calendar

pseudocode for gregorian calendar

String function examples, 1. De ne a function chomp :: String -> String tha...

1. De ne a function chomp :: String -> String that selects a run of repeated characters from the start of a string with the run being as long as possible. For example ch

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd