Queries to count distinct Binary Strings of all lengths from N to M satisfying given properties | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 1e5 + 5 ; const int MOD = 1000000007 ; long int dp [ N ] ; void countStrings ( int K , vector < vector < 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 . size ( ) ; i ++ ) { long int ans = dp [ Q [ i ] [ 1 ] ] - dp [ Q [ i ] [ 0 ] - 1 ] ; if ( ans < 0 ) ans = ans + MOD ; cout << ans << endl ; } } int main ( ) { int K = 3 ; vector < vector < int > > Q = { { 1 , 4 } , { 3 , 7 } } ; countStrings ( K , Q ) ; return 0 ; }