добрый день! решал задачу 104235F - Вероятность хорошей последовательности и мне стало очень интересно, почему мое решение не работает, и можно ли это как-то исправить
решал задачу комбинаторно, формула для решения: 1-С_k^4/k**n, но на 27 тесте решение ломается, решал на питоне и возможно вся проблема в том, что числа такого большого порядка воспринимаются питоном как бесконечность, из-за чего при n>20 или n<k формула просто выдает 1, мне хотелось бы разобраться в данном вопросе, и узнать как же все таки решить эту задачу математически.
Формула неправильная, потому что те массивы, в которых есть $$$c$$$ таких возрастающих подотрезков, ты посчитаешь ровно $$$c$$$ раз, а нужно, понятное дело, 1. Самый простой контртест: $$$5 \text{ } 5$$$, где плохую последовательность $$$(1, 2, 3, 4, 5)$$$ ты вычтешь 2 раза вместо одного.
Сомневаюсь, что здесь есть чисто комбинаторное решение, проще уж написать какое-то дп (адекватного решения формулой включений-исключений тоже не видно)
решение через рандом — наше всё
спасибо за подробный ответ! действительно, в предоставленном Вами контртесте учитывается две подпоследовательности. попробую вывести формулу исходя из других соображений.