How to solve the following problem?

Revision en1, by X-O__O-X, 2020-10-12 12:33:40

Given n and k where

0 <= n <= 10^5 and

1 <= k <= min(n, 10^5) and k is even

A nice string of length n is a binary string such that for all substrings of length k, number of 1s equal number of 0s.

let c_i equal number of 1s in the i_th valid string — (k/2)

Compute summation ( 2 ^ c_i ) for all nice strings, modulo 1000000007.

example n=6, k=4

one nice string is 001100 -> c_i = 2 — 2 = 0 -> 2^c_i = 1

another nice string is 101010 -> c_i = number of 1s — k/2 = 3 — 2 = 1 -> 2^c_i = 2

yet another example is 110011 -> c_i = number of 1s — k/2 = 4 — 2 = 2 -> 2^c_i = 4

010101-> 1

101010 -> 1

011001-> 1

100110 > 1

ans = (1+2+4+1+1+1+1) % 1000000007 = 11

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English X-O__O-X 2020-10-12 12:33:40 769 Initial revision (published)