Number of ways to color N | Java program for the above approach ; Function to count the ways to color block ; For storing powers of 2 ; For storing binomial coefficient values ; Calculating binomial coefficient using DP ; Calculating powers of 2 ; Sort the indices to calculate length of each section ; Initialise answer to 1 ; Find the length of each section ; Merge this section ; Return the final count ; Driver Code ; Number of blocks ; Number of colored blocks ; Function call
import java . util . * ; class GFG { static int mod = 1000000007 ; static int waysToColor ( int arr [ ] , int n , int k ) { int powOf2 [ ] = new int [ 500 ] ; int [ ] [ ] c = new int [ 500 ] [ 500 ] ; for ( int i = 0 ; i <= n ; i ++ ) { c [ i ] [ 0 ] = 1 ; for ( int j = 1 ; j <= i ; j ++ ) { c [ i ] [ j ] = ( c [ i - 1 ] [ j ] + c [ i - 1 ] [ j - 1 ] ) % mod ; } } powOf2 [ 0 ] = powOf2 [ 1 ] = 1 ; for ( int i = 2 ; i <= n ; i ++ ) { powOf2 [ i ] = powOf2 [ i - 1 ] * 2 % mod ; } int rem = n - k ; arr [ k ++ ] = n + 1 ; Arrays . sort ( arr ) ; int answer = 1 ; for ( int i = 0 ; i < k ; i ++ ) { int x = arr [ i ] - ( i - 1 >= 0 ? arr [ i - 1 ] : 0 ) - 1 ; answer *= c [ rem ] [ x ] % mod * ( i != 0 && i != k - 1 ? powOf2 [ x ] : 1 ) % mod ; rem -= x ; } return answer ; } public static void main ( String [ ] args ) { int N = 6 ; int K = 3 ; int arr [ ] = { 1 , 2 , 6 , 0 } ; System . out . print ( waysToColor ( arr , N , K ) ) ; } }