STRCOUNT - Counting binary strings

no tags 

Let f(n,k) is the number of length n binary strings for which the length of the longest substring of ones is equal to k. You have to build a table of these values.

Input

None.

Output

63 lines - the n-th of them consists of n+1 values: f(n,0) f(n,1) ... f(n,n).

Example

1 1
1 2 1
1 4 2 1
1 7 5 2 1
...

hide comments
kshubham02: 2019-07-20 22:11:55

Why isn't .txt a valid file format for solution of this problem?

megumitadokoro: 2018-03-18 08:25:07

It took me 4h to check every corner cases. At least I've got AC in one go. But clearly, remember to check EVERY corner cases in a dp problem. The solution is short, but you have to be very careful and know exactly what you have in mind.

buttman: 2016-08-20 05:41:57

Last edit: 2016-08-20 05:42:50
xxbloodysantaxx: 2015-07-17 21:11:05

Really after so long I did it :)

Ravi kumar: 2015-04-11 12:20:28

recursion+memo AC in first attempt :)

upper me: 2013-12-17 11:53:47

getting TLE with top-bottom approach :(

张翼德: 2012-10-28 09:48:36

got AC at my first try with bottom-up iterations :D :D

Ajey Golsangi: 2012-07-25 15:17:44

@romal thoppilan : The ans for n = 7 , k = 2 is 47 whereas your output says 46. Write a brute force checker to check outputs upto some limit.

(^_^): 2012-02-17 20:32:27

code id 6522023 please check the code. I am getting WA. Can you kindly check why I am getting WA??
Please reply!!!


Added by:Noszi
Date:2011-09-20
Time limit:0.102s
Source limit:3333B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:folklore