Про модули уже отвечено, я расскажу, как решать эту задачу быстрее, чем полным перебором.
Пусть общее количество карт - N.
Для простоты понимания, давайте забудем про колоду, просто карты раздаются как-то в 2 кучки по N/2 карт. Это пригодится попозже. Удобнее не вероятность считать, а количество способов раздать карты. Потом надо будет поделить количество хороших способов на все способы.
Сразу комбинаторно подсчитаем, сколько всего способов есть. Это просто количество всех различных колод. Гуглите "перестановки с повторениями". Формула будет такой:
N!/ a[1]! ... a[n]!
Раз мы на это число в конце будем делить, то сразу же считайте перевернутую формулу: подсчитайте факториал числа всех карт по модулю, обратите, умножьте на все маленькие факториалы.
Теперь самое главное, подсчитаем количество способов раздать карты так, что у всех поровну уникальных карт.
Динамическое программирование DP(k, t, i, j) - сколько способов раздать первые k типов карт так, что у первого игрока t карт всего, из них i уникальных, а у второго игрока j уникальных карт (при этом мы знаем, сколько у него всего карт -
a[1]+...+a[k] - t).
База:
DP(0,0,0,0) = 1,
DP(0,*,*,*) = 0
Ответ:
sum {i=1..n} DP(n, N/2, i, i)
Пересчет:
DP(k,t,i,j) = sum{v=0..min(a[k],t)} DP(k-1, t-v, i - {v>0}, j-{v < a[k]}) * C(t, v) * C(a[1]+a[2]+...+a[k]-t, a[k]-v)
Тут надо объяснить: мы перебираем, сколько карт последнего типа досталось первому игроку: v. Это все разные колоды, поэтому их надо суммировать. Как бы убираем все карты этого последнего типа из рассмотрения. Что остается? То же самое ДП, но типов на 1 меньше, у первого игрока на v карт меньше и уникальные карты надо уменьшить на 1, если какому-то игроку хоть одна карта досталась. Но есть еще множители - это количество сочетаний. Эти самые v карт последнего типа могут быть на любом из t мест в колоде у первого игрока. Аналогично для второго игрока. Тут надо умножать, потому что любую колоду из предыдущего состояния ДП можно разбавить картами последнего типа в разных позициях и все эти способы дадут разные результирующие колоды. Надо домножить на оба сочетания, потому что мы независимо можем тасовать карты у первого и второго игрока.
Сочетания считаются факториалами
С(n,k) = n!/ k! (n-k)!.
Я бы посоветовал предподсчитать все факториалы до 500 по модулю в массив, а так же обратные к ним.
Еще, если не будет влезать по памяти, обратите внимание, что в ДП достаточно хранить лишь 2 слоя по первому параметру. Т.е. надо места для 2*500*50*50 элементов, что для 4-х байтных значений будет занимать ~10mb памяти. Может даже long long можно хранить. Но тут надо переписать ДП снизу вверх, а не рекурсивно. Просто посмотрите, какие состояния куда плюсуются и с какими множителями. В этом случае вы будете не убирать карты последнего типа, а добавлять карты нового типа. Опять же, перебирайте сколько кому этих карт достанется. Надо только осторожно смотреть множители - С(сколько карт после добавления, сколько добавили).
Теперь прикинем на коленке сложность вычислений таким алгоритмом.
Само ДП имеет состояний 50*500*50*50 и пересчет 11 вариантов. Если все перемножить, получается что-то меньше 700 миллионов - в одну-две секунды должно влезать.
Полный перебор у вас, занимает что-то типа 11^50 - никогда не дождетесь на сколько нибудь не тривиальном тесте.
