405546: GYM101991 F Flipping El-fetiera

Memory Limit:1024 MB Time Limit:10 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Flipping El-fetieratime limit per test10 secondsmemory limit per test1024 megabytesinputfetiera.inoutputstandard output

Fouad was craving for Fetiera, so he went to a Fetier restaurant and ordered one. The chef told him that he sells a square Fetiera in the form of a N × N matrix.

On the surface of the Fetiera, there is one Semsema on each 1 × 1 cell of the Fetiera. Each Semsema can be either on the top side or the bottom side of the Fetira, but he cannot have two Semsemas in one cell on both sides.

Fouad loves to watch the chef flipping Fetiera, and this one was way more interesting than usual. The chef chooses a random (uniformly at random) rectangular submatrix and flips it in place. Whenever he flips a submatrix of the Fetira, the Semsemas which were on top will be on the bottom and vice versa.

Given the initial state of the Fetiera, and knowing that the chef did the flipping K times, Fouad was wondering how many Semsemas will be on the top side of it. Therefore, he is asking you to help him find the expected number of Semsemas on the top side.

Input

The first line of input contains a single integer T specifying the number of test cases.

Each test case begins with a line containing two space-separated integers N and K (1 ≤ N ≤ 300, 0 ≤ K ≤ 300), in which N is the size of the Fetiera matrix, and K is the number of flipping operations.

Then N lines follow, each line i contains N space-separated values Fi1, ..., FiN (), in which Fij representing the top side of the jth cell in the ith row of the Fetiera (1 means the Semsema is on the top side and 0 means the Semsema is on the bottom side in the initial configuration).

Output

For each test case, print a single line containing a single decimal number (rounded to exactly 5 decimal places) representing the expected number of Semsemas on the Fetiera after making the flipping operation for exactly K times. The output will be checked with a relative error.

ExampleInput
2
4 2
1 0 1 1
0 0 0 1
1 0 0 0
0 0 0 0
3 3
1 1 1
0 0 0
1 0 0
Output
7.57280
4.58728

加入题单

上一题 下一题 算法标签: