Queries to count distinct Binary Strings of all lengths from N to M satisfying given properties | Python3 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
N = int ( 1e5 + 5 ) NEW_LINE MOD = 1000000007 NEW_LINE dp = [ 0 ] * N NEW_LINE def countStrings ( K , Q ) : NEW_LINE INDENT dp [ 0 ] = 1 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT dp [ i ] = dp [ i - 1 ] NEW_LINE if ( i >= K ) : NEW_LINE INDENT dp [ i ] = ( dp [ i ] + dp [ i - K ] ) % MOD NEW_LINE DEDENT DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT dp [ i ] = ( dp [ i ] + dp [ i - 1 ] ) % MOD NEW_LINE DEDENT for i in range ( len ( Q ) ) : NEW_LINE INDENT ans = dp [ Q [ i ] [ 1 ] ] - dp [ Q [ i ] [ 0 ] - 1 ] NEW_LINE if ( ans < 0 ) : NEW_LINE INDENT ans += MOD NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT DEDENT K = 3 NEW_LINE Q = [ [ 1 , 4 ] , [ 3 , 7 ] ] NEW_LINE countStrings ( K , Q ) NEW_LINE