Смуга (Розбір)

Нехай маємо $w$ білих квадратів і $k$ груп чорних квадратів.

Оскільки групи чорних квадратів не торкаються одна одної, то між ними обов'язково має бути принаймні одна біла клітинка. Тобто повинно існувати як мінімум k - 1 білих квадратів. Якщо w < k - 1, то розмістити групи неможливо, і відповідь дорівнює $0$.

Поділимо білі клітинки на два типи:

• Обов'язкові k - 1 білих клітинок, які стоять між чорними групами;

• Вільні — решта w - (k - 1) білих клітинок.

Ці вільні білі клітинки можна розподіляти довільно в будь-якому місці щодо груп чорних квадратів.

Вільні білі клітинки можна розміщувати в наступних місцях:

• перед першою чорною групою;

• між групами;

• після останньої чорної групи.

Кількість усіх таких місць дорівнює k + 1.

Визначимо комбінаторну модель:

• у нас є w - (k - 1) вільних однакових білих клітинок;

• вільні білі клітинки слід розподілити по k + 1 різним місцям;

• обмеження на кількість білих клітинок в кожному місці відсутні;

Це класична задача сполучень з повтореннями (starts bars).

Відомо, що розподілити $n$ однакових об'єктів по $k$ різним місцям без обмежень на кількість об'єктів в кожному місці можна C_{n+k-1}^{k-1} способами.

Тоді в нашому випадку розподілити w - (k - 1) однакових білих клітинок по k + 1 різним місцям можна C_{(w - (k - 1)) + k + 1 - 1}^k = C_{w + 1}^k способами.

Приклад

Розглянемо другий тест. Існує $3$ смуги довжини $5$ з кодом $12$:

Загальна кількість чорних клітинок: s = 1 + 2 = 3.

Кількість білих клітинок: w = n - s = 5 - 3 = 2.

Між групами обов'язково має бути принаймні одна біла клітинка.

• Кількість обов'язкових білих клітинок дорівнює k - 1 = 1;

• Кількість вільних білих клітинок дорівнює w - (k - 1) = 2 - 1 = 1;

Для $1$ вільної білої клітинки є k + 1 = 3 місця.

Розподілити $1$ вільну білу клітинку по $3$ місцям можна C_3^2 = 3 способами.

Реалізація алгоритму

Читаємо вхідні дані.

t = int(input())
for _ in range(t):
  data = list(map(int, input().split()))
  n = data[0]
  k = data[1]

При k = 0 відповідь $1$.

  if k == 0:
    print(1)
    continue

Отримуємо код для прямокутника $code$.

  code = data[2:]

Обчислюємо кількість білих квадратів $w$ в смузі.

  s = sum(code)
  w = n – s

Якщо w < k - 1, то розмістити групи неможливо, і відповідь дорівнює $0$.

  if w < k - 1:
    print(0)
    continue

Обчислюємо і виводимо відповідь.

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

Java реалізація

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)));
     }
  }
}