Lemur Partiləri - əsas#11269

Lemur Partiləri - əsas (Həll təhlili)

n yerə bəzi növlər iki lemurla, bəziləri isə bir lemurla təmsil olunacaq. i cüt lemur (yəni i növləri iki fərdlə təmsil olunur) seçək. Belə seçim C_k^i üsulla edilə bilər. Bundan sonra VIP zonasında n - 2i boş yer qalacaq. Bu yerlərdən qalan k - i növlərindən hər birindən bir lemur seçərək istifadə etmək olar. Belə lemurları seçmə üsullarının sayı C_k - i^n - 2i düsturu ilə hesablanır.

Belə ki, i dəyəri 0-dan k-yə qədər hər hansı bir tam dəyər ala bilər, buna görə də yekun cavabı mümkün olan bütün i-lərə əsaslanaraq toplama ilə alırıq:

i = 0 \sum k C_{k}^{i} \cdot C_{k - i}^{n - 2 i}

\sum_{i = 0}^k C_k^i \cdot C_{k - i}^{n - 2i}

Misal

2-ci misal üzərində düşünək, burada k = 4 cüt lemur və VIP zonada n = 3 yer var. Düstura əsasən:

i = 0 \sum k C_{4}^{i} \cdot C_{4 - i}^{3 - 2 i} = C_{4}^{0} \cdot C_{4}^{3} + C_{4}^{1} \cdot C_{3}^{1} = 4 + 12 = 16

\sum_{i = 0}^k C_4^i \cdot C_{4 - i}^{3 - 2i} = C_4^0 \cdot C_4^3 + C_4^1 \cdot C_3^1 = 4 + 12 = 16

Yalnız sıfır olmayan toplananları çıxaraq. C_n^k dəyərini sıfır qəbul edirik, əgər üç bərabərsizliklərdən biri həyata keçse: k < 0, n < 0 və ya k > n.

Lemurları {a, a, b, b, c, c, d, d} kimi hərflərlə ifadə edək, burada eyni hərflər bir növ lemura uyğun gəlir.

C_4^0 C_4^3 = 4 həddinə uyğun gələn vəziyyət, heç bir növün cüt lemurunun seçilməməsi, yəni seçilmiş üç lemurun fərqli növlərə aid olduğu vəziyyətdir. Mümkün dörd seçim belədir:

C_4^1 C_3^1 = 12 toplananı üzərində düşünək. Bu halda bir növdən iki lemur seçilir (bu seçimin 4 variantı var). Qalan bir yerə qalan üç növdən birindən bir lemur seçilir. Bu üsullarla ümumi 12 müxtəlif variant mümkündür:

İki fərqli növdən iki lemura üçün 3 yerə yerləşdirmək açıq-aşkar ki, mümkün deyil. Buna görə də, qalan toplama elementlərinin hamısı sıfıra bərabərdir.

Alqoritmin reallaşdırılması

Sabitləri elan edək.

#define MAX 1000001
#define MOD 1000000007

Massivləri elan edək:

fact modulu MOD ilə alınmış ədəd faktoriyallarını saxlayır;
factinv modulu MOD ilə alınmış ədəd faktoriyalarının qarşı işarələnmə dəyərlərini saxlayır:

fact[n] = n! mod 1000000007
factinv[n] = n! -1 mod 1000000007

typedef long long ll;
ll fact[MAX], factinv[MAX];

pow funksiyası modulla ədədi qüvvətə yüksəldir: $x^{n} m o d p$ x^n~mod~p.

ll pow(ll x, ll n, ll p)
{
  if (n == 0) return 1;
  if (n % 2 == 0) return pow((x * x) % p, n / 2, p);
  return (x * pow(x, n - 1, p)) % p;
}

inverse funksiyası x ədədinin sadə modul p-dakı qarşı işarələnmiş miqdarını tapır. Çünki p sadə bir ədəddir, Fermatın kiçik teoremi ilə belə bir bərabərlik mövcuddur:

x^{p - 1} m o d p = 1 u ¨ c \c u ¨ n h ə r 1 \leq x < p

x^{p-1}~mod~p~=~1~üçün~hər~1 \le x < p

Bu bərabərlik dəyişilə bilər:

(x \cdot x^{p - 2}) m o d p = 1,

(x \cdot x^{p-2})~mod~p~=~1,

buradan x-ə qarşı işarələnən miqdarın x^p-2 mod p olduğu nəticələnir.

ll inverse(ll x, ll p)
{
  return pow(x, p - 2, p);
}

Cnk funksiyası binomik koeffisiyentin dəyərini belə bir formuladan hesablayır:

C_{n}^{k} = \frac{n !}{k ! ( n - k )!}

C_n^k = \frac{n!}{k! (n - k)!}

ll Cnk(int n, int k)
{
  return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
}

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

scanf("%d %d", &k, &n);

Faktoriyal massivlərini fact və factinv dolduraq.

fact[0] = 1;
for (i = 1; i < MAX; i++)
  fact[i] = (fact[i - 1] * i) % MOD;

factinv[0] = 1;
for (i = 1; i < MAX; i++)
   factinv[i] = inverse(fact[i], MOD);

C++

_i = 0^k C_k^i C_k - i^n - 2i formuluna əsasən cavabı hesablayaq. Binomik koeffisiyentin C_n^k dəyərini 0 hesab edək, əgər üç şərtdən biri ödənirsə: k < 0, n < 0 və ya k > n.

res = 0;
for (i = 0; i <= k; i++)
{
  if (n - 2 * i < 0 || k - i < 0 || n - 2 * i > k - i) continue;
  res = (res + Cnk(k, i) * Cnk(k - i, n - 2 * i)) % MOD;
}

Cavabı çıxarmaq.

printf("%lld\n", res);