popabogdannnn's blog

Counting Problem
By popabogdannnn, history, 6 years ago, In English

Hello guys! Recently I took part in Reply Challenges Coding Contest and there was an interesting counting problem I couldn't find its solution. It goes like this: You are given N <= 10^9 and M <= 1100 and a binary string B of length M. Count how many binary strings A of length N exist such that A does not contain B as a substring. Output the answer mod 10^9 + 7. During the contest we had a 4 min span of running an input and giving its answer, so not so fast solutions could work, however I would prefer the fastest solution to this, but any idea is welcomed by me. Original statement: https://challenges.reply.com/tamtamy/file/download-95022.action Thank you!

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This is a standard DP problem. We first formulate the DP(i,j) as the number of string formed by first i characters of A such that currently j characters have matched form B.

Transitions are quite trivial if you are familiar with kmp algorithm's failure function.

Now this would give TLE as you have O(n*m > 10^12) complexity.We can improve upon this a bit with the given constraints.

we can calculate the the above DP using matrix exponentiation too. O(m^3*logn = 10^9*32 ). Just use the j as the current state and see the transitions to other state on 0 and 1.

We can use faster techniques to calculate linear recurrences to get better complexity. calculate the first 2*m terms and put in Berlekamp–Massey algorithm. I think that would get you answer in the Desired time.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please verify the problem's link? I can't seem to open it.

→ Reply