Как рассчитать ЧРЕЗВЫЧАЙНО большие биномиальные коэффициенты по простому числу?

Эта проблемаответом оказывается вычисление больших биномиальных коэффициентов по модулю простого числа с использованием Теорема Лукаса. Вот решение этой проблемы с использованием этой техники: Вот.

Теперь мои вопросы:

  • Похоже, мой код истекает, если данные увеличиваются из-за переполнения переменных. Есть ли способы справиться с этим?
  • Есть ли способы сделать это без использования этого теорема?

РЕДАКТИРОВАТЬ: обратите внимание, что, как это OI или ACM проблема, внешние библиотеки кроме оригинальных не допускаются.

Код ниже:

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

#define N 100010

long long mod_pow(int a,int n,int p)
{
long long ret=1;
long long A=a;
while(n)
{
if (n & 1)
ret=(ret*A)%p;
A=(A*A)%p;
n>>=1;
}
return ret;
}

long long factorial[N];

void init(long long p)
{
factorial[0] = 1;
for(int i = 1;i <= p;i++)
factorial[i] = factorial[i-1]*i%p;
//for(int i = 0;i < p;i++)
//ni[i] = mod_pow(factorial[i],p-2,p);
}

long long Lucas(long long a,long long k,long long p)
{
long long re = 1;
while(a && k)
{
long long aa = a%p;long long bb = k%p;
if(aa < bb) return 0;
re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-2,p)%p;
a /= p;
k /= p;
}
return re;
}

int main()
{
int t;
cin >> t;
while(t--)
{
long long n,m,p;
cin >> n >> m >> p;
init(p);
cout << Lucas(n+m,m,p) << "\n";
}
return 0;
}

1

Решение

Это решение предполагает, что п2 вписывается в unsigned long long, С unsigned long long имеет по крайней мере 64 бита в соответствии со стандартом, это работает по крайней мере для п до 4 миллиардов, гораздо больше, чем указывает вопрос.

typedef unsigned long long num;

/* x such that a*x = 1 mod p */
num modinv(num a, num p)
{
/* implement this one on your own */
/* you can use the extended Euclidean algorithm */
}

/* n chose m mod p */
/* computed with the theorem of Lucas */
num modbinom(num n, num m, num p)
{
num i, result, divisor, n_, m_;

if (m == 0)
return 1;

/* check for the likely case that the result is zero */
if (n < m)
return 0;

for (n_ = n, m_ = m; m_ > 0; n_ /= p, m_ /= p)
if (n_ % p < m_ % p)
return 0;

for (result = 1; n >= p || m >= p; n /= p, m /= p) {
result *= modbinom(n % p, m % p, p);
result %= p;
}

/* avoid unnecessary computations */
if (m > n - m)
m = n - m;

divisor = 1;
for (i = 0; i < m; i++) {
result *= n - i;
result %= p;

divisor *= i + 1;
divisor %= p;
}

result *= modinv(divisor, p);
result %= p;

return result;
}
2

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

Целое число с бесконечной точностью кажется подходящим.

Если вы находитесь в C ++,
библиотека PicklingTools имеет целое число «бесконечной точности» (аналогично
Длинный тип Python). Кто-то еще предложил Python, это разумно
ответь, если знаешь Python. если вы хотите сделать это в C ++, вы можете
используйте тип int_n:

#include "ocval.h"int_n n="012345678910227836478627843";
n = n + 1;   // Can combine with other plain ints as well

Посмотрите документацию по адресу:

http://www.picklingtools.com/html/usersguide.html#c-int-n-and-the-python-arbitrary-size-ints-long

а также

http://www.picklingtools.com/html/faq.html#c-and-otab-tup-int-un-int-n-new-in-picklingtools-1-2-0

Загрузка для C ++ PicklingTools Вот.

0

Вы хотите bignum (А.к.а. арифметика произвольной точности) библиотека.

Во-первых, не пишите свою собственную библиотеку bignum (или bigint), потому что эффективные алгоритмы (более эффективные, чем наивные, которые вы изучали в школе) сложно разработать и реализовать.

Тогда я бы порекомендовал GMPlib. Это бесплатное программное обеспечение, хорошо документированное, часто используемое, довольно эффективное и хорошо спроектированное (возможно, с некоторыми недостатками, в частности невозможностью подключить свой собственный распределитель памяти вместо системы) malloc; но вам, вероятно, все равно, если вы не хотите поймать редкое состояние нехватки памяти …). Это легко Интерфейс C ++. Он упакован в большинстве дистрибутивов Linux.

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

0

Предположим, что нам нужно вычислить значение (a / b) mod p где p это простое число. поскольку p простое тогда каждое число b имеет обратный мод p, Так (a / b) mod p = (a mod p) * (b mod p)^-1, Мы можем использовать евклидов алгоритм для вычисления обратного.

Получить (n over k) нам нужно вычислить n! mod p, (k!)^-1, ((n - k)!)^-1, Общая сложность времени O(n),

ОБНОВИТЬ: Вот код на C ++. Я не проверял это всесторонне все же.

int64_t fastPow(int64_t a, int64_t exp, int64_t mod)
{
int64_t res = 1;
while (exp)
{
if (exp % 2 == 1)
{
res *= a;
res %= mod;
}

a *= a;
a %= mod;
exp >>= 1;
}
return res;
}

// This inverse works only for primes p, it uses Fermat's little theorem
int64_t inverse(int64_t a, int64_t p)
{
assert(p >= 2);
return fastPow(a, p - 2, p);
}

int64_t binomial(int64_t n, int64_t k, int64_t p)
{
std::vector<int64_t> fact(n + 1);
fact[0] = 1;
for (auto i = 1; i <= n; ++i)
fact[i] = (fact[i - 1] * i) % p;

return ((((fact[n] * inverse(fact[k], p)) % p) * inverse(fact[n - k], p)) % p);
}
0