Zolaq (Həll təhlili)

Qoy $w$ ağ kvadrat, $k$ qara kvadrat qrupları mövcuddur.

Qara kvadrat qrupları bir-birinə toxunmadığı üçün onların arasında ən az bir ağ kvadrat olmalıdır. Yəni ən az k - 1 ağ kvadrat mövcud olmalıdır. Əgər w < k - 1 olarsa, qrupları yerləşdirmək mümkün deyil və cavab $0$-a bərabərdir.

Ağ kvadratları iki növə bölək:

• Qara qrupların arasında olan məcburi k - 1 ağ kvadrat;

• Azad — qalan w - (k - 1) ağ kvadrat.

Bu azad ağ kvadratlar qara kvadrat qruplarına münasibətdə istənilən yerdə sərbəst paylana bilər.

Azad ağ kvadratları aşağıdakı yerlərdə yerləşdirmək olar:

• birinci qara qrupun əvvəlində;

• qruplar arasında;

• son qara qrupdan sonra.

Bütün bu yerlərin sayı k + 1-ə bərabərdir.

Kombinator modelini təyin edək:

• w - (k - 1) bərabər azad ağ kvadratımız var;

• azad ağ kvadratları k + 1 müxtəlif yerə paylamaq lazımdır;

• hər yerdəki ağ kvadratların sayına məhdudiyyət qoyulmur;

Bu, təkrarlanma ilə kombinasiyalar məsələsi (starts bars) klassik məsələdir.

Məlumdur ki, $n$ bərabər obyektləri $k$ müxtəlif yerə, hər yerdəki obyektlərin sayına məhdudiyyət olmadan paylamaq C_{n+k-1}^{k-1} şəkildə həyata keçirə bilər.

Onda bizim halda w - (k - 1) bərabər ağ kvadratı k + 1 müxtəlif yerə paylamaq C_{(w - (k - 1)) + k + 1 - 1}^k = C_{w + 1}^k şəkildə mümkündür.

Misal

İkinci testə baxaq. Uzunluğu $5$ olan $3$ zolaq $12$ kodu ilə mövcuddur:

Qara kvadratların ümumi sayı: s = 1 + 2 = 3.

Ağ kvadratların sayı: w = n - s = 5 - 3 = 2.

Qruplar arasında ən az bir ağ kvadrat olmalıdır.

• Məcburi ağ kvadratların sayı k - 1 = 1;

• Azad ağ kvadratların sayı w - (k - 1) = 2 - 1 = 1;

$1$ azad ağ kvadrat üçün k + 1 = 3 yer mövcuddur.

$1$ azad ağ kvadrat $3$ yerə C_3^2 = 3 şəkildə paylana bilər.

Algoritminin reallaşdırılması

Giriş verilərini oxuyuruq.

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

k = 0 halda cavab $1$-dir.

  if k == 0:
    print(1)
    continue

Düzbucaq üçün kodu əldə edirik.

  code = data[2:]

Zolaqda ağ kvadratların sayını $w$ hesablayırıq.

  s = sum(code)
  w = n – s

Əgər w < k - 1, qrupları yerləşdirmək mümkün deyil və cavab $0$-a bərabərdir.

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

Cavabı hesablayırıq və çıxışa yazırıq.

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

Java reallaşdırılması

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