Counting Problem

Revision en1, by popabogdannnn, 2019-03-18 12:51:25

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: Thank you!

Tags #dp, #counting, #combinatorics


  Rev. Lang. By When Δ Comment
en1 English popabogdannnn 2019-03-18 12:51:25 685 Initial revision (published)