Compute nCr % p | Set 2 ( Lucas Theorem ) | A Lucas Theorem based solution to compute nCr % p ; Returns nCr % p . In this Lucas Theorem based program , this function is only called for n < p and r < p . ; The array C is going to store last row of pascal triangle at the end . And last entry of last row is nCr ; 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 ) ; ; Lucas Theorem based function that returns nCr % p This function works like decimal to binary conversion recursive function . First we compute last digits of n and r in base p , then recur for remaining digits ; Base case ; Compute last digits of n and r in base p ; Compute result for last digits computed above , and for remaining digits . Multiply the two results and compute the result of multiplication in modulo p . return ( nCrModpLucas ( n / p , r / p , p ) * Last digits of n and r nCrModpDP ( ni , ri , p ) ) % p ; Remaining digits ; Driver program
class GFG { static int nCrModpDP ( int n , int r , int p ) { int [ ] C = new int [ r + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = Math . min ( i , r ) ; j > 0 ; j -- ) C [ j ] = ( C [ j ] + C [ j - 1 ] ) % p ; } return C [ r ] ; } static int nCrModpLucas ( int n , int r , int p ) { if ( r == 0 ) return 1 ; int ni = n % p ; int ri = r % p ; } public static void main ( String [ ] args ) { int n = 1000 , r = 900 , p = 13 ; System . out . println ( " Value ▁ of ▁ nCr ▁ % ▁ p ▁ is ▁ " + nCrModpLucas ( n , r , p ) ) ; } }