ncr_modulo_p.cpp File Reference

This program aims at calculating nCr modulo p. More...

#include <cassert>
#include <iostream>
#include <vector>

Include dependency graph for ncr_modulo_p.cpp:

Go to the source code of this file.

Classes
class	math::ncr_modulo_p::NCRModuloP
	Class which contains all methods required for calculating nCr mod p. More...

Namespaces
namespace	math
	for assert
namespace	ncr_modulo_p
	Functions for nCr modulo p implementation.
namespace	utils
	this namespace contains the definitions of the functions called from the class math::ncr_modulo_p::NCRModuloP

Functions
int64_t	math::ncr_modulo_p::utils::gcdExtended (const int64_t &a, const int64_t &b, int64_t &x, int64_t &y)
	finds the values x and y such that a*x + b*y = gcd(a,b)
int64_t	math::ncr_modulo_p::utils::modInverse (const int64_t &a, const int64_t &m)
static void	tests ()
	tests math::ncr_modulo_p::NCRModuloP
void	example ()
	example showing the usage of the math::ncr_modulo_p::NCRModuloP class
int	main ()

Detailed Description

This program aims at calculating nCr modulo p.

nCr is defined as n! / (r! * (n-r)!) where n! represents factorial of n. In many cases, the value of nCr is too large to fit in a 64 bit integer. Hence, in competitive programming, there are many problems or subproblems to compute nCr modulo p where p is a given number.

Author

Kaustubh Damania

Definition in file ncr_modulo_p.cpp.

Function Documentation

example()

void example

(

)

example showing the usage of the math::ncr_modulo_p::NCRModuloP class

Definition at line 175 of file ncr_modulo_p.cpp.

               {
    const int64_t size = 1e6 + 1;
    const int64_t p = 1e9 + 7;
 
    // the ncrObj contains the precomputed values of factorials modulo p for
    // values from 0 to size
    const auto ncrObj = math::ncr_modulo_p::NCRModuloP(size, p);
 
    // having the ncrObj we can efficiently query the values of (n C r)%p
    // note that time of the computation does not depend on size
    for (int i = 0; i <= 7; i++) {
        std::cout << 6 << "C" << i << " mod " << p << " = " << ncrObj.ncr(6, i)
                  << "\n";
    }
}

gcdExtended()

int64_t math::ncr_modulo_p::utils::gcdExtended	(	const int64_t &	a,
		const int64_t &	b,
		int64_t &	x,
		int64_t &	y )

finds the values x and y such that a*x + b*y = gcd(a,b)

Parameters

[in]	a	the first input of the gcd
[in]	a	the second input of the gcd
[out]	x	the Bézout coefficient of a
[out]	y	the Bézout coefficient of b

Returns

the gcd of a and b

Definition at line 44 of file ncr_modulo_p.cpp.

                                {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
 
    int64_t x1 = 0, y1 = 0;
    const int64_t gcd = gcdExtended(b % a, a, x1, y1);
 
    x = y1 - (b / a) * x1;
    y = x1;
    return gcd;
}

main()

int main

(

void

)

Definition at line 191 of file ncr_modulo_p.cpp.

           {
    tests();
    example();
    return 0;
}

modInverse()

int64_t math::ncr_modulo_p::utils::modInverse	(	const int64_t &	a,
		const int64_t &	m )

Find modular inverse of a modulo m i.e. a number x such that (a*x)m = 1

Parameters

[in]	a	the number for which the modular inverse is queried
[in]	m	the modulus

Returns

the inverce of a modulo m, if it exists, -1 otherwise

Definition at line 66 of file ncr_modulo_p.cpp.

                                                       {
    int64_t x = 0, y = 0;
    const int64_t g = gcdExtended(a, m, x, y);
    if (g != 1) {  // modular inverse doesn't exist
        return -1;
    } else {
        return ((x + m) % m);
    }
}

tests()

static void tests ( )

static

tests math::ncr_modulo_p::NCRModuloP

Definition at line 142 of file ncr_modulo_p.cpp.

                    {
    struct TestCase {
        const int64_t size;
        const int64_t p;
        const int64_t n;
        const int64_t r;
        const int64_t expected;
 
        TestCase(const int64_t size, const int64_t p, const int64_t n,
                 const int64_t r, const int64_t expected)
            : size(size), p(p), n(n), r(r), expected(expected) {}
    };
    const std::vector<TestCase> test_cases = {
        TestCase(60000, 1000000007, 52323, 26161, 224944353),
        TestCase(20, 5, 6, 2, 30 % 5),
        TestCase(100, 29, 7, 3, 35 % 29),
        TestCase(1000, 13, 10, 3, 120 % 13),
        TestCase(20, 17, 1, 10, 0),
        TestCase(45, 19, 23, 1, 23 % 19),
        TestCase(45, 19, 23, 0, 1),
        TestCase(45, 19, 23, 23, 1),
        TestCase(20, 9, 10, 2, -1)};
    for (const auto& tc : test_cases) {
        assert(math::ncr_modulo_p::NCRModuloP(tc.size, tc.p).ncr(tc.n, tc.r) ==
               tc.expected);
    }
 
    std::cout << "\n\nAll tests have successfully passed!\n";
}