1537. Stripe

A rectangle of size 1×n is given, divided into 1×1 cells. Each cell can be colored either white or black.

The code of this rectangle is defined as a sequence of numbers, each of which is equal to the number of consecutive black cells when the rectangle is viewed from left to right.

For example, the code of the rectangle shown above is 2 3 2 8 1. The number of white cells is not taken into account; moreover, each group of black cells must be separated from the next one by at least one white cell. Therefore, the same code may correspond to several different rectangles. In particular, the following rectangle also has the given code:

Determine the number of rectangles that correspond to the given code.

Input. The first line contains the number of test cases t (1 < t < 20). Each of the following t lines describes one test case and contains:

· the length of the rectangle n (1 ≤ n ≤ 200);

· the number of elements in the code k (0 ≤ k ≤ (n + 1) / 2) ;

· k integers describing the code.

Output. For each test case, print in a separate line the number of rectangles that correspond to the given code.

Sample input	Sample output
3 4 0 5 2 1 2 4 2 2 2	1 3 0

SOLUTION

combinatorics

Algorithm analysis

Let there be w white squares and k groups of black squares.

Since the groups of black squares do not touch each other, there must be at least one white square between any two groups. Therefore, there must be at least k – 1 white squares. If w < k – 1, then it is impossible to place the groups, and the answer is 0.

Let us divide the white cells into two types:

· The mandatory k – 1 white cells that are placed between the groups of black squares;

· The free white cells – the remaining w – (k – 1) white cells.

These free white cells can be distributed arbitrarily anywhere relative to the groups of black squares.

The free white cells can be placed in the following positions:

· before the first black group;

· between the groups;

· after the last black group.

The total number of such positions is k + 1.

Let us define a combinatorial model:

· we have w – (k – 1) identical free white cells;

· these free white cells must be distributed among k + 1 distinct positions;

· there are no restrictions on the number of white cells in each position;

This is a classic problem of combinations with repetition (starts & bars).

It is well known that distributing n identical objects among k distinct positions with no restrictions on the number of objects in each position can be done in ways.

Therefore, in our case, distributing w – (k – 1) identical white cells among k + 1 distinct positions can be done in = ways.

Example

Let us consider the second test. There are 3 strips of length 5 with code 1 2:

The total number of black cells is s = 1 + 2 = 3.

The number of white cells is w = n – s = 5 – 3 = 2.

There must be at least one white cell between the groups.

· The number of mandatory white cells is k – 1 = 1;

· The number of free white cells is w – (k – 1) = 2 – 1 = 1;

For 1 free white cell, there are k + 1 = 3 possible positions.

Distributing 1 free white cell among 3 positions can be done in = 3 ways.

Algorithm implementation

Read the input data.

t = int(input())

for _ in range(t):

data = list(map(int, input().split()))

n = data[0]

k = data[1]

For k = 0, the answer is 1.

if k == 0:

print(1)

continue

Extract the code for the rectangle code.

code = data[2:]

Compute the number of white squares w in the strip.

s = sum(code)

w = n – s

If w < k – 1, then it is impossible to place the groups, and the answer is 0.

if w < k - 1:

print(0)

continue

Compute and print the answer.

print(math.comb(w + 1, k))

Java implementation

import java.util.*;

import java.math.*;

public class Main

{

static BigInteger Cnk(BigInteger n, BigInteger k)

{

BigInteger ONE = BigInteger.ONE, CnkRes = ONE;

if (k.compareTo(n.subtract(k)) > 0) k = n.subtract(k);

for(BigInteger i = ONE; i.compareTo(k) <= 0; i = i.add(ONE))

CnkRes = CnkRes.multiply(n.subtract(i).add(ONE)).divide(i);

return CnkRes;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

int group[] = new int[200];

while(tests-- > 0)

{

int n = con.nextInt(), g = con.nextInt();

int w = 0;

for(int j = 0; j < g; j++)

{

group[j] = con.nextInt();

w += group[j];

}

w = n - w;

if (w < g - 1) System.out.println("0");

else System.out.println(Cnk(BigInteger.valueOf(w+1),

BigInteger.valueOf(w-g+1)));

}

}

}