Что интересно, эту задачу можно решить намного оптимальнее, чем предложено как в статье, так и в других комментариях (я не нашёл чего-то существенно лучше ): например, за .
Для формальности пусть наш кубик будет не обычный игральный, а с числами .
Заметим, что нам достаточно найти – количество способов набрать сумму , после бросков. Тогда вероятность можно получить, разделив на .
Подставив разные результаты выпадения последнего кубика, получаем .
Заметим, что это просто коэффициент многочлена при .
Я не умею эффективно находить в отдельности -й коэффициент, поэтому давайте найдём многочлен целиком.
Для этого воспользуемся бинарным возведением в степень: это позволит нам найти искомый многочлен всего за перемножений многочленов. Перемножать многочлены можно при помощи быстрого преобразованием Фурье за . Итоговая асимптотика: .
С небольшими изменениями это же решение можно использовать для кубиков разных размеров (например, для бросков d125 и бросков d512).
Что интересно, эту задачу можно решить намного оптимальнее, чем предложено как в статье, так и в других комментариях (я не нашёл чего-то существенно лучше
): например, за 
.
Для формальности пусть наш кубик будет не обычный игральный, а с числами
.
Заметим, что нам достаточно найти
– количество способов набрать сумму 
, после 
бросков. Тогда вероятность можно получить, разделив 
на 
.
Подставив разные результаты выпадения последнего кубика, получаем
.
Заметим, что
это просто коэффициент многочлена 
при 
.
Я не умею эффективно находить в отдельности
-й коэффициент, поэтому давайте найдём многочлен целиком.
Для этого воспользуемся бинарным возведением в степень: это позволит нам найти искомый многочлен всего за
перемножений многочленов. Перемножать многочлены можно при помощи быстрого преобразованием Фурье за 
.
.
Итоговая асимптотика:
С небольшими изменениями это же решение можно использовать для кубиков разных размеров (например, для
бросков d125 и 
бросков d512).