Compute nCr % p | Set 1 ( Introduction and Dynamic Programming Solution ) | A Dynamic Programming based solution to compute nCr % p ; Returns nCr % p ; Optimization for the cases when r is large ; The array C is going to store last row of pascal triangle at the end . And last entry of last row is nCr ; Top row of Pascal Triangle ; One by constructs remaining rows of Pascal Triangle from top to bottom ; Fill entries of current row using previous row values ; nCj = ( n - 1 ) Cj + ( n - 1 ) C ( j - 1 ) ; ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int nCrModp ( int n , int r , int p ) { if ( r > n - r ) r = n - r ; int C [ r + 1 ] ; memset ( C , 0 , sizeof ( C ) ) ; C [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = min ( i , r ) ; j > 0 ; j -- ) C [ j ] = ( C [ j ] + C [ j - 1 ] ) % p ; } return C [ r ] ; } int main ( ) { int n = 10 , r = 2 , p = 13 ; cout << " Value ▁ of ▁ nCr ▁ % ▁ p ▁ is ▁ " << nCrModp ( n , r , p ) ; return 0 ; }