Təkrarlarla kombinasiyalar#11723

Təkrarlarla kombinasiyalar (Həll təhlili)

Bu məsələ, daşınmanın təkrarlanması ilə birləşmələrin sayının hesablanmasına, yəni bu tənliyin həllinə gətirilir:

x_{1} + x_{2} + ... + x_{k} = n,

x_1 + x_2 + ...+ x_k = n,

burada

$x_{i}$ x_i — $i$ -ci yerdə yerləşdirilən obyektlərin sayı,
$k$ — yerlərin sayı.
$n$ — obyektlərin ümumi sayı.

Hər bir $x_{i}$ x_i qeyri-mənfi tam ədəd ola bilər. Bu tənliyin həllərinin sayı aşağıdakı düsturla təyin olunur (eolymp məsələsi $11551$ ): $C_{n + k - 1}^{k - 1}$ C_{n+k-1}^{k-1}.

Nümunə

Birinci nümunədə ( $k = 3, n = 4$ k = 3, n = 4) cavab $C_{6}^{2} = (6 \cdot 5) /2 = 15$ C_6^2 = (6 \cdot 5) / 2 = 15.

İkinci nümunədə ( $k = 3, n = 2$ k = 3, n = 2) cavab $C_{4}^{2} = (4 \cdot 3) /2 = 6$ C_4^2 = (4 \cdot 3) / 2 = 6.

Alqoritmin reallaşdırılması

Daimiləri və binominal əmsalın dəyərlərinin yadda saxlanması üçün $d p$ massivini təyin edək.

#define MAX 201
#define MOD 1000000007
long long dp[MAX][MAX];

Cnk funksiyası $C_{n}^{k}$ C_n^k binominal əmsalının $M O D = 1 0^{9} + 7$ MOD = 10^9 + 7 ilə modul alınmış dəyərini hesablayır.

long long Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  if (dp[n][k] != -1) return dp[n][k];
  return dp[n][k] = (Cnk(n - 1, k - 1) + Cnk(n - 1, k)) % MOD;
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d %d", &k, &n);
memset(dp, -1, sizeof(dp));

$C_{n + k - 1}^{k - 1}$ C_{n + k - 1}^{k - 1} dəyərini hesablayır və nəticəni çıxarırıq.

printf("%lld\n", Cnk(n + k - 1, k - 1));