A. Число сочетаний

Условие

Даны два целых числа n и k ($0 \leq k \leq n \leq 20$).

Выведите число сочетаний из n по k.

$$C^k_n = \frac{n!}{k! * (n − k)!}$$

Идея

Посчитаем влоб

#include <iostream>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    cout << fact(n) / (fact(k) * fact(n - k));
}

Факториал можно посчитать несколькими способами:

  • Циклично
    long long fact(int n){
      long long result=1;
      for (int i = n; i> 1; i--){
         result = result*i;
      }
      return result;
    }
    
  • Рекурсивно

    long long fact(int n) {
      return n*fact(n-1);
    }
    
  • Заметим, что в нашей задаче нужно посчитать 3 факториала. Можно оптимизировать задачу рассчёта, запомнив все промежуточные значения факториала в дополнительной структуре данных.

#include <unordered_map>

unordered_map<int, long long> fact_m = {{0, 1},
                                  {1, 1}};

long long fact(int x) {
    if (fact_m.count(x) == 0) {
        fact_m[x] = fact(x - 1) * x;
    }
    return fact_m[x];
}

Все решения заходят

Решение

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<int, long long> fact_m = {{0, 1},
                                  {1, 1}};

long long fact(int x) {
    if (fact_m.count(x) == 0) {
        fact_m[x] = fact(x - 1) * x;
    }
    return fact_m[x];
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << fact(n) / (fact(k) * fact(n - k));
}

B. Треугольник Паскаля

Условие

Дано целое число $n$ ($1 \leq n \leq 67$).

Требуется $n$ строк Треугольника Паскаля

\begin{matrix} n=0: & & & & & 1 & & & &\\ n=1: & & & & 1 & & 1 & & &\\ n=2: & & & 1 & & 2 & & 1 & &\\ n=3: & & 1 & & 3 & & 3 & & 1 &\\ n=4: & 1 & & 4 & & 6 & & 4 & & 1\\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots & \end{matrix}

Идея

Зная формулу $$C^k_n=C^{k}_{n-1} + C^{k-1}_{n-1},$$ и то, что

  1. $ C^0_n = 1 $ – способов не выбрать ничего из любого множества
  2. $ C^n_n = 1 $ – способов выбрать всё из любого множества
  3. $ C^1_n = n $ – способов выбрать 1 элемент из любого множества

Получим

Решение

#include <iostream>
#include <vector>

#define ull unsigned long long

using namespace std;


int main() {
    int n;
    cin >> n;
    vector<ull> next, current = {1};
    cout << 1 << endl;

    for (int j = 1; j < n; ++j) {
        next = {1};
        cout << next[0] << " ";
        for (int i = 1; i < current.size(); ++i) {
            ull c = current[i] + current[i - 1];
            next.push_back(c);
            cout << c << " ";
        }
        next.push_back(1);
        cout << 1 << endl;

        current = next;
    }
}

C. Число размещений

Условие

По заданным целым числам n и k требуется вычислить число размещений.

Идея

Число размещений определяется формулой $$A^m_n = \frac{n!}{(n-m)!} = n*(n-1)*\dots*(n-m+1)$$

Решение

  • Влоб (используем функция факториала)
#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<int, long long> fact_m = {{0, 1},
                                        {1, 1}};

long long fact(int x) {
    if (fact_m.count(x) == 0) {
        fact_m[x] = fact(x - 1) * x;
    }
    return fact_m[x];
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << fact(n) / fact(n - k);
}
  • Экономно
#include <iostream>

using namespace std;


int main() {
    int n, k;
    cin >> n >> k;
    long long result = 1;
    for(int i = n-k+1; i<=n ; ++i){
        result *= i;
    }
    cout << result;
}

D. Коробки

Условие

Необходимо вычислить количество способов разложить $n$ шариков по $m$ различным коробкам. При этом возможно в некоторых коробках не будет шариков. Все шарики считаются одинаковыми.

В первой строке содержаться два числа – $n$ и $m$, $1 \leq m, n \leq 20$.

Идея

Типичная задача на сочетания с повторениями! $$\hat{C}^k_n = \frac{(n+k-1)!}{k!*(n-1)!} = C^{n-1}_{n + k -1}$$

Однако если попробовать решить задачу влоб (прямо по формуле), мы столкнёмся с переполнением любого целочисленного типа. Задача допускает рассчёт $39!$!

Для рассчёта не влоб нужно заметить, что $$A^m_n = \frac{n!}{(n-m)!}$$ $$C^k_n = \frac{n!}{k! * (n − k)!} = \frac{A^{n-k}_n}{k!} = \frac{A^k_n}{(n-k)!}$$

Решение

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<int, unsigned long long> fact_m = {{0, 1},
                                                 {1, 1}};

unsigned long long fact(int x) {
    if (fact_m.count(x) == 0) {
        fact_m[x] = fact(x - 1) * (unsigned long long) x;
    }
    return fact_m[x];
}


int main() {
    int n, k;
    unsigned long long res = 1;
    cin >> n >> k;
    int l = min(k, n + 1);
    int m = max(k, n + 1);
    for (int i = m; i <= n + k - 1; i++) {
        res *= i;
    }
    res /= fact(l - 1);
    cout << res;
    return 0;
}

E. Карточки

Условиe

На день рождения Пете подарили набор карточек с буквами. Теперь Петя с большим интересом составляет из них разные слова. И вот, однажды, составив очередное слово, Петя заинтересовалcя вопросом: "А сколько различных слов можно составить из тех же карточек, что и данное?". Помогите ему ответить на этот вопрос.

Идея

Задача на перестановки с повторениями (пример 5 из лекции про комбинаторику)

$$P_{k_1,k_2,\dots,k_n} = \frac{P_n}{P_{k_1}*P_{k_2}*\dots*P_{k_n}} = \frac{n!}{k_1! * k_2! * \dots k_n!}$$

Решение

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<int, unsigned long long> fact_m = {{0, 1},
                                                 {1, 1}};

unsigned long long fact(int x) {
    if (fact_m.count(x) == 0) {
        fact_m[x] = fact(x - 1) * (unsigned long long) x;
    }
    return fact_m[x];
}


int main() {

    unordered_map<char, int> letters;
    string word;
    cin >> word;
    for (auto l : word) {
        letters[l]++;
    }

    unsigned long long transpositions = 1;
    for (auto pair : letters) {
        transpositions *= fact(pair.second);
    }
    cout << fact(word.length()) / transpositions;
    return 0;
}
In [ ]: