Special Subarrays

2.5

6 votes
Data Structures, Advanced Data Structures, Trie
Problem

An array is said to be special, if we can break it down into subarrays where every subarray (length > 1) starts and ends with 0 and rest all other numbers are 1.

Given N binary arrays.

Sam decided to write down all the distinct prefix subarrays of the given N binary arrays on a paper (he'll write distinct prefix only). After that he counts the number of special subarrays in every prefix and sum that up (a special subarray will be counted as many times as it is contained in each prefix). 

Find the sum found by Sam modulo 109+7.

Input Format:

  • The first line contains N denoting the number of binary arrays.
  • The ith of the next N lines contains the binary array in form of a string S[i].

Output Format:

Sum found by Sam modulo 109+7

Constraints:

1N1031S[i]1051Ni=1S[i]2×106

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There are 8 different unqiue prefixes, count of special subarray in each prefix is listed below

  • 0 -> 0 special subarrays
  • 1 -> 0 special subarrays
  • 10 -> 0 special subarrays
  • 00 -> 1 special subarray [0,0]
  • 001 -> 1 special subarray [0,0]
  • 0010 -> 2 special subarrays [0,0] and [0,1,0]
  • 00101 -> 2 special subarrays [0,0] and [0,1,0]
  • 001011 -> 2 special subarrays [0,0] and [0,1,0]
Editor Image

?