Проблема заключается в том, чтобы найти n-й каталонский номер mod m, где m НЕ простой, m = (10^14 + 7). Вот список методов, которые я пробовал: (max N = 10,000)
- Динамическое программирование для поиска таблиц, слишком медленно
- Использовать каталонскую формулу
ncr(2*n, n)/(n + 1), опять же она недостаточно быстро из-за функцииncr, не может ускорить использование возведения в степень возведения в степень, потому чтоmне является простым. - Hardcode - таблица предварительно сгенерированного
Catalans, но она не удалась из-за ограничения размера файла. - Отношение повторения
C(i,k) = C(i-1,k-1) + C(i-1,k), это слишком медленно.
Итак, я задаюсь вопросом, есть ли какой-нибудь другой более быстрый алгоритм для поиска n-го каталонского числа, о котором я не знаю?
Использование динамического программирования
void generate_catalan_numbers() {
catalan[1] = 1;
for (int i = 2; i <= MAX_NUMBERS; i++) {
for (int j = 1; j <= i - 1; j++) {
catalan[i] = (catalan[i] + ((catalan[j]) * catalan[i - j]) % MODULO) % MODULO;
}
catalan[i] = catalan[i] % MODULO;
}
}
Использование исходной формулы
ull n_choose_r(ull n, ull r) {
if (n < r)
return 0;
if (r > n/2) {
r = n - r;
}
ull result = 1;
ull common_divisor;
for (int i = 1; i <= r; ++i) {
common_divisor = gcd(result, i);
result /= common_divisor;
result *= (n - i + 1) / (i / common_divisor);
}
return result;
}
Использование рекуррентного отношения
ull n_choose_r_relation(ull n, ull r) {
for (int i = 0; i <= n + 1; ++i) {
for (int k = 0; k <= r && k <= i; ++k) {
if (k == 0 || k == i) {
ncr[i][k] = 1;
}
else {
ncr[i][k] = (ncr[i - 1][k - 1] + ncr[i - 1][k]) % MODULO;
}
}
}
return ncr[n][r];
}
.