Всем привет, подскажите, кто сможет: Не могу сообразить, как решить задачу (вычислительно, естественно, не на листке):

Найти все комбинации m по n, при этом m и n могут быть очень большими, вплоть до нескольких тысяч.
Вернуть нужно otvet modulo 1 000 000, соответственно. 
Конечно, просто применить обычную формулу сочетаний с такими числами я не могу, а других вариантов не знаю.

Заранее спасибо.

Файл много страничный.

Присоединённый файл ( Кол-во скачиваний: 15 )
 2000.tif 559,93 Kb

Спасибо, увы, плюсануть не дает форум, но это то, что нужно.

Сейчас плюсанем.   

Тему можно закрывать, задачу решил. 
Подход из файла товарища Pavia работает. Кратко, общая суть для ленивых:

Сокращаем m! снизу и n! сверху. (например снизу 3!, сверху 6!, после сокращения снизу будет 1, сверху 4 * 5 * 6).
Далее раскладываем числитель (уже) и знаменатель на множители. Ищем общий делитель для каждой пары числителя и знаменателя и сокращаем, до тех пор, пока в знаменателе не останутся одни единицы. В рамках этой задачи это возможно всегда.
В итоге останется только последовательность множителей в числителе. Ну, дальше я просто использовал длинную арифметику. Может и есть способ лучше 

с треугольником Паскаля, ИМХО, проще

(естественно, там всё надо считать по модулю)

А как его использовать в данной задаче?

m-е число в n-й строке треугольника как раз и равно количеству сочетаний из n по m

сам треугольник просто иллюстрирует схему для вычисления количеств сочетаний:

сначала вычисляем одну строку - C(0,0)=1
а на каждой следующей первое и последнее число приравниваем 1, а внутри используем формулу C(n,m)=C(n-1,m)+C(n-1,m-1)

(ну и всё это по модулю)

Обалдеть, не знал о его таких свойствах, нехило 
Я умею вычислять треугольник Паскаля, огромное вам спасибо.