Как решить проблему nCr%p

Постановка задачи

Нам даны три целых числа n, r и p, мы должны найти значение nCr%p. Здесь p — натуральное число, большее n, а nCr — биномиальный коэффициент.

Примеры

Вход: n = 10, r = 2, p = 13

Выходные данные: 6

Пояснения: 10C2 равно 45, а 45 % 13 равно 6.

Существует множество способов решения этой задачи, но в этом блоге мы рассмотрим только 3 из них, так как, по нашему мнению, они наиболее просты для понимания.

Подход грубой силы

Подход грубой силы очень прост, просто найдите nCr данного числа, возьмите моду этого числа на p и выведите результат.

Для решения nCr мы будем использовать одно из свойств комбинаций.

nCr = n-1Cr-1 + n-1Cr
Приведенный ниже код представляет собой реализацию метода перебора с использованием рекурсии.

package com.Tekolio.Extras
// solve nCr%p
public class solve_cobnimatrics_1 {
    public static void main(String[] args) {
        int n = 5;
        int r = 2;
        int p = 13;
       System.out.print("Value of "+n+"C"+r+" % "+p+" is "+solve(n, r, p));
    }
    public static int solve(int A, int B, int C) {
        if (B > A) // the value of r can never be greater than n
            return 0;
        if (B == 0 || B == A) // 0C0 = 1 & nCn = 1
            return 1;
        return (solve(A - 1, B - 1, C)%C + solve(A - 1, B, C)%C)%C;
    }
}

Вывести

Значение 5C2 % 13 равно 10

Временная сложность: O(n*max(r ,n-r))

Вспомогательное пространство: O(n*max(r, n-r))

Но есть одна проблема с этим кодом. Этот код хорошо подходит для нахождения значения nCr только тогда, когда значения n и r малы, как в нашем примере. Как только мы попробуем использовать этот код для больших значений n и r, например, n=50 и r=40, результат переполнится, и мы даже не успеем взять моду этого значения.

Существует еще одна проблема, с которой мы можем столкнуться при использовании этого кода. Эта проблема не такая большая, как вышеописанная, но все же о ней следует помнить. При выполнении рекурсии иногда функция вычисляет одну и ту же подпроблему снова и снова. Смотрите рисунок ниже

Как видно из приведенного выше изображения, мы имеем 3C1 два раза и 2C1 три раза, что делает его решением перекрывающихся подпроблем.

Чтобы справиться с этим перекрытием, а также найти эффективное решение, мы будем использовать динамическое программирование.

Читать далее…