Queries to count distinct Binary Strings of all lengths from N to M satisfying given properties | Javascript 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
let N = parseInt ( ( 1e5 + 5 ) ) ; let MOD = 1000000007 ; let dp = Array ( N ) . fill ( 0 ) ; function countStrings ( K , Q ) { dp [ 0 ] = 1 ; for ( let i = 1 ; i < N ; i ++ ) { dp [ i ] = dp [ i - 1 ] ; if ( i >= K ) dp [ i ] = ( dp [ i ] + dp [ i - K ] ) % MOD ; } for ( let i = 1 ; i < N ; i ++ ) { dp [ i ] = ( dp [ i ] + dp [ i - 1 ] ) % MOD ; } for ( let i = 0 ; i < Q . length ; i ++ ) { var ans = dp [ Q [ i ] [ 1 ] ] - dp [ Q [ i ] [ 0 ] - 1 ] ; if ( ans < 0 ) ans = ans + MOD ; document . write ( ans + " " ) ; } } var K = 3 ; let Q = [ [ 1 , 4 ] , [ 3 , 7 ] ] ; countStrings ( K , Q ) ;