Рассчитать коэффициент многочлена

Question

Рассчитать коэффициент многочлена

Я хочу посчитать коэффициент многочлена мод 1e9 + 7. Он равен: n! / (k0! * k1! * k2 * … * км!)

В моем случае m = 3, k0 + k1 + k2 = n, так что это будет: n! / (k0! * k1! * k2!) Мой код для этого:

....
long long k2 = n - k1 - k0;
long long dans = fact[n] % MOD;
long long tmp = fact[i] % MOD;
tmp = (tmp * fact[j]) % MOD;
tmp = (tpm * fact[k]) % MOD;
res = (fact[n] / tmp) % MOD; // mb mistake is here...
cout << res;

факт [i] — факториал i mod 1e9 + 7
Не работает на больших тестах

3

algebra c++combinatorics

Решение

Другие решения

Вы можете рассчитать сумма (кс)! / (к1! * ... * кн!) умножив числитель вниз от sum(ks) и деление в знаменателе от 1, Результат по мере продвижения всегда будет целым числом, потому что вы делите на i только после первого умножения i смежные целые числа.

def multinomial(*ks):
""" Computes the multinomial coefficient of the given coefficients
>>> multinomial(3, 3)
20
>>> multinomial(2, 2, 2)
90
"""result = 1
numerator = sum(ks)
ks = list(ks)       # These two lines are unnecessary optimizations
ks.remove(max(ks))  # and can be removed
for k in ks:
for i in range(k):
result *= numerator
result //= i + 1
numerator -= 1
return result

3

Недавно я столкнулся с этой проблемой, и мое решение было сначала сопоставить с пространством для журналов, выполнить работу там, а затем отобразить обратно. Это полезно, поскольку мы избегаем проблем переполнения в пространстве журнала, а также умножения становятся суммами, которые могут быть более эффективными. Также может быть полезно работать непосредственно с результатом пространства журнала.

Математика:

C(x1, ..., xn) = sum(x)! / (x1! * ... * xn!)

Следовательно

ln C(x1, ..., xn) = ln sum(x)! - ln {(x1! * ... * xn!)}
= sum{k=1->sum(x)} ln k - sum(ln xi!)
= sum{k=1->sum(x)} ln k - sum(sum{j=1->xi} (ln j))

Если какой-либо из xi, или же sum(x) большие (например,> 100), тогда мы могли бы просто использовать приближение Стерлинга:

ln x! ~= x * ln x - x

Что бы дать:

ln C(x1, ..., xn) ~= sum(x) * ln sum(x) - sum(x) - sum(xi * ln xi - xi)

Вот код Полезно сначала написать вспомогательную функцию журнала факториала.

#include <vector>
#include <algorithm>   // std::transform
#include <numeric>     // std::iota, std:: accumulate
#include <cmath>       // std::log
#include <type_traits> // std::enable_if_t, std::is_integral, std::is_floating_point

template <typename RealType, typename IntegerType,
typename = std::enable_if_t<std::is_floating_point<RealType>::value>,
typename = std::enable_if_t<std::is_integral<IntegerType>::value>>
RealType log_factorial(IntegerType x)
{
if (x == 0 || x == 1) return 0;
if (x == 2) return std::log(2); // can add more for efficiency

if (x > 100) {
return x * std::log(x) - x; // Stirling's approximation
} else {
std::vector<IntegerType> lx(x);
std::iota(lx.begin(), lx.end(), 1);
std::vector<RealType> tx(x);
std::transform(lx.cbegin(), lx.cend(), tx.begin(),
[] (IntegerType a) { return std::log(static_cast<RealType>(a)); });
return std::accumulate(tx.cbegin(), tx.cend(), RealType {});
}
}

Тогда логарифмическая функция проста:

template <typename RealType, typename IntegerType>
RealType log_multinomial_coefficient(std::initializer_list<IntegerType> il)
{
std::vector<RealType> denoms(il.size());
std::transform(il.begin(), il.end(), denoms.begin(), log_factorial<RealType, IntegerType>);
return log_factorial<RealType>(std::accumulate(il.begin(), il.end(), IntegerType {})) -
std::accumulate(denoms.cbegin(), denoms.cend(), RealType {});
}

И, наконец, метод полиномиального коэффициента:

template <typename RealType, typename IntegerType>
IntegerType multinomial_coefficient(std::initializer_list<IntegerType> il)
{
return static_cast<IntegerType>(std::exp(log_multinomial_coefficient<RealType, IntegerType>(std::move(il))));
}

например

cout << multinomial_coefficient<double, long long>({6, 3, 3, 5}) << endl; // 114354240

Для любых входных данных, намного превышающих этот, мы собираемся переполнить встроенными типами, но мы все равно можем получить результат пространства журнала, например,

cout << log_multinomial_coefficient<double>({6, 3, 11, 5, 10, 8}) << endl; // 65.1633

1

Источник

Accepted Answer

Я надеюсь, что я не занимаюсь ссылками здесь, но вот процесс работы, чтобы решить вашу проблему:

Наивные реализации всегда будут страдать от ошибок переполнения. Вы должны быть готовы использовать некоторые математические свойства полиномиального коэффициента для достижения надежного решения. Дэйв Барбер делает это в своем библиотека, где используется рекурсивное свойство (пример для 4 чисел — рекурсия останавливается, когда все ветви заменяются на ноль)
```
multi (a, b, c, d) = multi (a − 1, b, c, d) + multi (a, b − 1, c, d) + multi (a, b, c − 1, d) + multi (a, b, c, d − 1)
```
На основании вышеизложенного, Давид Серрано Мартинес показывает, как реализация это обеспечивает контроль переполнения может быть разделен. Его код можно использовать так же легко, как
```
unsigned long long result_2 = multinomial::multi<unsigned long long>({9, 8, 4});
```
Третий вариант — использовать (или учиться) библиотеки, которые предназначены для комбинаторики, например, ПОДМНОЖЕСТВО. Это немного более сложный код для чтения из-за зависимостей и длины, но вызов так же прост, как
```
int factors[4] = {1, 2, 3, 4};
Maths::Combinatorics::Arithmetic::multinomial(4, factors)
```

3