How to calculate EXTREMELY big binomial coefficients modulo by prime number?

Question

This problem's answer turns out to be calculating large binomial coefficients modulo prime number using Lucas' theorem. Here's the solution to that problem using this technique: here.

Now my questions are:

• Seems like my code expires if the data increases due to overflow of variables. Any ways to handle this?
• Are there any ways to do this without using this theorem?

EDIT: note that as this is an OI or ACM problem, external libs other than original ones are not permitted.

Code below:

#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;
}

Answer 1

This solution assumes that p² fits into an unsigned long long. Since an unsigned long long has at least 64 bits as per standard, this works at least for p up to 4 billion, much more than the question specifies.

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;
}