Generating prefix - sum of hash of a
mul [ 0 ] = 1 ; hash_a [ 0 ] = ( a [ 0 ] - 97 ) % mod ; for ( int i = 1 ; i < a . size ( ) ; i ++ ) { mul [ i ] = ( mul [ i - 1 ] * d ) % mod ; hash_a [ i ] = ( hash_a [ i - 1 ] + mul [ i ] * ( a [ i ] - 97 ) ) % mod ; } }