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:

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

Namespaces
namespace	math
	for std::rand
namespace	ncr_modulo_p
	Functions for nCr modulo p implementation.

Functions
static void	tests (math::ncr_modulo_p::NCRModuloP ncrObj)
	Test implementations. More...
int	main ()
	Main function. More...

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

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    // populate the fac array
    const uint64_t size = 1e6 + 1;
    const uint64_t p = 1e9 + 7;
    math::ncr_modulo_p::NCRModuloP ncrObj =
        math::ncr_modulo_p::NCRModuloP(size, p);
    // test 6Ci for i=0 to 7
    for (int i = 0; i <= 7; i++) {
        std::cout << 6 << "C" << i << " = " << ncrObj.ncr(6, i, p) << "\n";
    }
    tests(ncrObj);  // execute the tests
    std::cout << "Assertions passed\n";
    return 0;
}

tests()

static void tests ( math::ncr_modulo_p::NCRModuloP  ncrObj )

static

Test implementations.

Parameters

ncrObj

object which contains the precomputed factorial values and ncr function

Returns

void

                                                     {
    // (52323 C 26161) % (1e9 + 7) = 224944353
    assert(ncrObj.ncr(52323, 26161, 1000000007) == 224944353);
    // 6 C 2 = 30, 30%5 = 0
    assert(ncrObj.ncr(6, 2, 5) == 0);
    // 7C3 = 35, 35 % 29 = 8
    assert(ncrObj.ncr(7, 3, 29) == 6);
}

Here is the call graph for this function: