Цитата(UndeadBlow @ 8.4.2013, 23:50  ) |
| Спасибо, увы, плюсануть не дает форум, но это то, что нужно. |
Сейчас плюсанем.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Сочетания с очень большими числами |
| Автор: UndeadBlow 8.4.2013, 22:16 |
| Всем привет, подскажите, кто сможет: Не могу сообразить, как решить задачу (вычислительно, естественно, не на листке): Найти все комбинации m по n, при этом m и n могут быть очень большими, вплоть до нескольких тысяч. Вернуть нужно otvet modulo 1 000 000, соответственно. Конечно, просто применить обычную формулу сочетаний с такими числами я не могу, а других вариантов не знаю. Заранее спасибо. |
| Автор: Pavia 8.4.2013, 22:26 |
| Файл много страничный. |
| Автор: UndeadBlow 8.4.2013, 22:50 |
| Спасибо, увы, плюсануть не дает форум, но это то, что нужно. |
| Автор: Фантом 8.4.2013, 23:03 | ||
Сейчас плюсанем. |
| Автор: UndeadBlow 9.4.2013, 19:50 |
| Тему можно закрывать, задачу решил. Подход из файла товарища Pavia работает. Кратко, общая суть для ленивых:  Сокращаем m! снизу и n! сверху. (например снизу 3!, сверху 6!, после сокращения снизу будет 1, сверху 4 * 5 * 6). Далее раскладываем числитель (уже) и знаменатель на множители. Ищем общий делитель для каждой пары числителя и знаменателя и сокращаем, до тех пор, пока в знаменателе не останутся одни единицы. В рамках этой задачи это возможно всегда. В итоге останется только последовательность множителей в числителе. Ну, дальше я просто использовал длинную арифметику. Может и есть способ лучше  |
| Автор: maxim1000 9.4.2013, 20:41 |
| с http://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B5%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA_%D0%9F%D0%B0%D1%81%D0%BA%D0%B0%D0%BB%D1%8F, ИМХО, проще (естественно, там всё надо считать по модулю) |
| Автор: UndeadBlow 9.4.2013, 20:58 | ||
А как его использовать в данной задаче? |
| Автор: maxim1000 10.4.2013, 07:55 |
| m-е число в n-й строке треугольника как раз и равно количеству сочетаний из n по m сам треугольник просто иллюстрирует схему для вычисления количеств сочетаний: сначала вычисляем одну строку - C(0,0)=1 а на каждой следующей первое и последнее число приравниваем 1, а внутри используем формулу C(n,m)=C(n-1,m)+C(n-1,m-1) (ну и всё это по модулю) |
| Автор: UndeadBlow 10.4.2013, 10:38 | ||
Обалдеть, не знал о его таких свойствах, нехило Я умею вычислять треугольник Паскаля, огромное вам спасибо. |