Count of N | Java Program to implement the above approach ; Function to calculate the total count of N - digit numbers such that the sum of digits at even positions and odd positions are divisible by A and B respectively ; For single digit numbers ; Largest possible number ; Count of possible odd digits ; Count of possible even digits ; Calculate total count of sequences of length even_count with sum divisible by A where first digit can be zero ; Calculate total count of sequences of length odd_count with sum divisible by B where cannot be zero ; Return their product as answer ; Driver Code
class GFG { public static long count ( int N , int A , int B ) { if ( N == 1 ) { return 9 / B + 1 ; } int max_sum = 9 * N ; int odd_count = N / 2 + N % 2 ; int even_count = N - odd_count ; long dp [ ] [ ] = new long [ even_count ] [ max_sum + 1 ] ; for ( int i = 0 ; i <= 9 ; i ++ ) dp [ 0 ] [ i % A ] ++ ; for ( int i = 1 ; i < even_count ; i ++ ) { for ( int j = 0 ; j <= 9 ; j ++ ) { for ( int k = 0 ; k <= max_sum ; k ++ ) { if ( dp [ i - 1 ] [ k ] > 0 ) dp [ i ] [ ( j + k ) % A ] += dp [ i - 1 ] [ k ] ; } } } long dp1 [ ] [ ] = new long [ odd_count ] [ max_sum + 1 ] ; for ( int i = 1 ; i <= 9 ; i ++ ) dp1 [ 0 ] [ i % B ] ++ ; for ( int i = 1 ; i < odd_count ; i ++ ) { for ( int j = 0 ; j <= 9 ; j ++ ) { for ( int k = 0 ; k <= max_sum ; k ++ ) { if ( dp1 [ i - 1 ] [ k ] > 0 ) dp1 [ i ] [ ( j + k ) % B ] += dp1 [ i - 1 ] [ k ] ; } } } return dp [ even_count - 1 ] [ 0 ] * dp1 [ odd_count - 1 ] [ 0 ] ; } public static void main ( String [ ] args ) { int N = 2 , A = 2 , B = 5 ; System . out . println ( count ( N , A , B ) ) ; } }