Queries to count distinct Binary Strings of all lengths from N to M satisfying given properties | Java program to implement the above approach ; Function to calculate the count of possible Strings ; Initialize dp [ 0 ] ; dp [ i ] represents count of Strings of length i ; Add dp [ i - k ] if i >= k ; Update Prefix Sum Array ; Driver Code
import java . util . * ; class GFG { static int N = ( int ) ( 1e5 + 5 ) ; static int MOD = 1000000007 ; static int [ ] dp = new int [ N ] ; static void countStrings ( int K , int [ ] [ ] Q ) { dp [ 0 ] = 1 ; for ( int i = 1 ; i < N ; i ++ ) { dp [ i ] = dp [ i - 1 ] ; if ( i >= K ) dp [ i ] = ( dp [ i ] + dp [ i - K ] ) % MOD ; } for ( int i = 1 ; i < N ; i ++ ) { dp [ i ] = ( dp [ i ] + dp [ i - 1 ] ) % MOD ; } for ( int i = 0 ; i < Q . length ; i ++ ) { int ans = dp [ Q [ i ] [ 1 ] ] - dp [ Q [ i ] [ 0 ] - 1 ] ; if ( ans < 0 ) ans = ans + MOD ; System . out . print ( ans + "NEW_LINE"); } } public static void main ( String [ ] args ) { int K = 3 ; int [ ] [ ] Q = { { 1 , 4 } , { 3 , 7 } } ; countStrings ( K , Q ) ; } }