Сочетания с очень большими числами

@UndeadBlow · Регистрация: 15.12.2011

Студворк — интернет-сервис помощи студентам

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

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

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

@UndeadBlow · 09.04.2013, 20:41 **[ТС]**

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

iifat · 12.04.2013, 17:41

Длинная арифметика не понадобится. Если нужен результат по модулю, то и все вычисления можно проводить по этому же модулю. Даже не знаю, стоит ли заморачиваться сокращениями; впрочем, если алгоритм уже есть и работает, может, и стоит.

zer0mail · 12.04.2013, 18:13

Алгоритм , конечно, можно улучшить. Но для радикального ускорения надо придумать, как делить по модулю...

Байт · 12.04.2013, 18:50

Сообщение от zer0mail

как делить по модулю..

Да... Если б 1000000 было простым числом, тогда вопросов нет. М.б. Великую Китайскую как-то попытаться использовать? Хотя вот так сразу ничего в голову не приходит.

Добавлено через 5 минут
Вот еще. Сократить на все двойки и пятерки (сократиться обязано, в знаменателе их не останется) а дальше - для каждой x, такой что НОД(x,5) = 1 и НОД(x,2) = 1 есть обратный по модулю 1000000.

Не по теме:

Это, конечно, не решение. Мысли вслух.

@UndeadBlow · 12.04.2013, 19:39 **[ТС]**

Сообщение от iifat

Длинная арифметика не понадобится. Если нужен результат по модулю, то и все вычисления можно проводить по этому же модулю. Даже не знаю, стоит ли заморачиваться сокращениями; впрочем, если алгоритм уже есть и работает, может, и стоит.

Я подумывал о вычислениях сразу по модулю, но не был уверен в этом свойстве, а проверять поленился.
Все работает и довольно шустро (я уверен, что можно лучше, но это уже намного лучше, чем я ожидал). У меня задача была такая, даны m и n. Нужно вычислить сумму всех комбинаций при k по n, где k от m до n, и вернуть по модулю 1млн. Ну вот при числах 928 и 1605, к примеру, мой компьютер (core i5) посчитал секунд за 10-20.

zer0mail · 12.04.2013, 20:19

А при числах 5000 и 10000?

@UndeadBlow · 12.04.2013, 21:11 **[ТС]**

Сообщение от zer0mail

А при числах 5000 и 10000?

В этом случае его нужно серьезно оптимизировать и распараллелить, иначе считаться будет очень долго.

@Somebody · 12.04.2013, 21:25

Треугольник Паскаля, не?

@UndeadBlow · 12.04.2013, 21:33 **[ТС]**

Сообщение от Somebody

Треугольник Паскаля, не?

Да.

240Volt · 12.04.2013, 22:41

Сообщение от UndeadBlow

просто применить обычную формулу сочетаний с такими числами я не могу

А предварительно преобразовать по Стирлингу?

iifat · 13.04.2013, 01:32

Ну, это всё же приближённая формула. Если нужен остаток, по идее, нужна точная.

240Volt · 13.04.2013, 11:08

Сообщение от iifat

Ну, это всё же приближённая формула.

Да, конечно. Но обратите внимание на величину погрешности.

zer0mail · 13.04.2013, 11:30

ТС нужен расчет для БОЛЬШИХ чисел. 4000! - это число ~10¹²⁶⁷³, при относительной погрешности z^-5 абсолютная всяко больше 10¹²⁰⁰⁰. Что уж говорить о точности по модулю 10⁶

iifat · 13.04.2013, 11:35

Вдруг дошло, что знаю самый быстрый способ: остаток от деления 25 и далее факториал на миллион равен нулю! Первые 24 проще посчитать заранее и хранить в таблице

zer0mail · 13.04.2013, 11:39

Число 1000! имеет порядок 10²⁵⁶⁷, что тоже дает очень-очень большую ошибку.

Нам нужен не сам факториал, а отношения факториалов типа: 1000!/27!*973!, поэтому выше я спрашивал, "как делить по модулю"

Байт · 13.04.2013, 11:41

Сообщение от iifat

остаток от деления 25 и далее факториал на миллион равен нулю

Более того, так себя ведет произведение 25-ти последовательных чисел.
ИМХО, собака зарыта где-то недалеко.

zer0mail · 13.04.2013, 11:54

C₁₀₀₀⁵⁰⁰ http://www.wolframalpha.com/in... 1%2F500%21

@Somebody · 13.04.2013, 12:06

Сообщение от UndeadBlow

Да.

Что "да"? По треугольнику даже для 10000 на самом старом процессоре моментально считается.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
 
int main()
{
   const unsigned modulus = 1000000;
   unsigned m, n;
   std::cin >> m >> n;
   if (n > m / 2)
      n = m - n;
   std::vector<unsigned> v(m + 1, 1);
   for (unsigned cm = 0; cm <= m; cm++)
      for (unsigned i = m + 1 - cm; i < m; i++)
         v[i] = (v[i] + v[i + 1]) % modulus;
   std::cout << v[n] << std::endl;
}

iifat · 13.04.2013, 12:08

Точно, поторопился. Забыл, что тут не факториалы, а сочетания.

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@UndeadBlow 8 / 6 / 1 Регистрация: 15.12.2011 Сообщений: 59

	Сочетания с очень большими числами 08.04.2013, 19:24. Показов 13152. Ответов 21 Метки нет (Все метки) Всем привет, подскажите, кто сможет: Не могу сообразить, как решить задачу (вычислительно, естественно, не на листке): Найти все комбинации m по n, при этом m и n могут быть очень большими, вплоть до нескольких тысяч. Вернуть нужно otvet modulo 1 000 000, соответственно. Конечно, просто применить обычную формулу сочетаний с такими числами я не могу, а других вариантов не знаю. Заранее спасибо. 0

@UndeadBlow 8 / 6 / 1 Регистрация: 15.12.2011 Сообщений: 59
	09.04.2013, 20:41 [ТС]
	Задачу решил, если кому понадобится, советую сократить факториал числителя и знаменателя, потом оставшееся разложить на множители, искать общий делитель в числителе и знаменателе, и сокращать, пока в знаменателе не останутся сплошные единицы. В рамках этой задачи это возможно всегда. Ну, а дальше или длинная арифметика или что похитрее. Код не буду выкладывать, он специфичен для моей задачи. 0

iifat 2904 / 1937 / 211 Регистрация: 05.06.2011 Сообщений: 5,724
	12.04.2013, 17:41
	Длинная арифметика не понадобится. Если нужен результат по модулю, то и все вычисления можно проводить по этому же модулю. Даже не знаю, стоит ли заморачиваться сокращениями; впрочем, если алгоритм уже есть и работает, может, и стоит. 2

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	12.04.2013, 18:13
	Алгоритм , конечно, можно улучшить. Но для радикального ускорения надо придумать, как делить по модулю... 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	12.04.2013, 20:19
	А при числах 5000 и 10000? 0

@Somebody 2838 / 1647 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	12.04.2013, 21:25
	Треугольник Паскаля, не? 0

iifat 2904 / 1937 / 211 Регистрация: 05.06.2011 Сообщений: 5,724
	13.04.2013, 01:32
	Ну, это всё же приближённая формула. Если нужен остаток, по идее, нужна точная. 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	13.04.2013, 11:30
	ТС нужен расчет для БОЛЬШИХ чисел. 4000! - это число ~10¹²⁶⁷³, при относительной погрешности z^-5 абсолютная всяко больше 10¹²⁰⁰⁰. Что уж говорить о точности по модулю 10⁶ 0

iifat 2904 / 1937 / 211 Регистрация: 05.06.2011 Сообщений: 5,724
	13.04.2013, 11:35
	Вдруг дошло, что знаю самый быстрый способ: остаток от деления 25 и далее факториал на миллион равен нулю! Первые 24 проще посчитать заранее и хранить в таблице 1

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	13.04.2013, 11:39
	Число 1000! имеет порядок 10²⁵⁶⁷, что тоже дает очень-очень большую ошибку. Нам нужен не сам факториал, а отношения факториалов типа: 1000!/27!*973!, поэтому выше я спрашивал, "как делить по модулю" 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	13.04.2013, 11:54
	C₁₀₀₀⁵⁰⁰ http://www.wolframalpha.com/in... 1%2F500%21 0

iifat 2904 / 1937 / 211 Регистрация: 05.06.2011 Сообщений: 5,724
	13.04.2013, 12:08
	Точно, поторопился. Забыл, что тут не факториалы, а сочетания. 0