Counting Problem

Правка en1, от 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: https://challenges.reply.com/tamtamy/file/download-95022.action Thank you!

Теги #dp, #counting, #combinatorics

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский popabogdannnn 2019-03-18 12:51:25 685 Initial revision (published)