День 5: Комбинаторика и по модулю простых чисел
Прошло много времени с момента моей последней публикации, и на самом деле это не четвертый день, но это не должно иметь большого значения, я обещаю, что так будет до 30-го дня.
Поэтому я часто сталкиваюсь с проблемами в онлайн-соревнованиях (Codeforces, FB Hacker Cup, Code Jam, Snackdown), которые требуют некоторых знаний комбинаторики. Большинство из них можно легко идентифицировать, но самая сложная часть - получить окончательный ответ в форме, которую можно легко запрограммировать и эффективно вычислить.
Так что для тех, у кого не было формального введения в комбинаторику, просто воспользуйтесь Google, есть много хороших ресурсов. Вот с чего нужно начать:
Простые перестановки и комбинации
Я всегда путала« перестановку и комбинацию - что и что? Вот простой способ запомнить: перестановка… betterexplained.com »
Прежде всего, давайте посмотрим, как вычислить факториалы для больших чисел, например 100 !, мы не можем хранить их в int или long long int (C ++), поэтому мы используем массив для хранения отдельных цифр и вычисляем факториал с помощью метода умножения ( добавляю и несу) мы учились в школе. Вот хороший пример:
Теперь во многих задачах вам нужно будет найти N choose r Modulo P, где P - простое число. Есть два популярных способа их вычисления:
- Использование теоремы Лукаса
Если вы хотите познакомиться с теоремой Лукаса, это отличный ресурс (ха-ха!):
2. Использование малой теоремы Ферма (модульная обратная).
Знать больше :
Если вы дошли до этого места, у вас было бы неплохое представление о комбинаторике в соревнованиях CP, так что вот хорошая проблема, с которой я столкнулся сегодня, которая побудила меня написать на эту тему (Хорошая DP + Комбинаторика):
Ссылка на мой код с комментариями:
Это все, ребята.
