Stripe (Editorial)

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 C_{n+k-1}^{k-1} ways.

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

Example

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

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 C_3^2 = 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)));
     }
  }
}