popabogdannnn's blog

By popabogdannnn, history, 7 months ago, , 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! #dp, Comments (3)
 » 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.
•  » » Thank you very much!
 » Could you please verify the problem's link? I can't seem to open it.