STRCOUNT - Counting binary strings

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
...

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

hide comments
2019-07-20 22:11:55
Why isn't .txt a valid file format for solution of this problem?
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.
2015-07-17 21:11:05 xxbloodysantaxx
Really after so long I did it :)
2015-04-11 12:20:28 Ravi kumar
recursion+memo AC in first attempt :)
2013-12-17 11:53:47 upper me
getting TLE with top-bottom approach :(
2012-10-28 09:48:36 张翼德
got AC at my first try with bottom-up iterations :D :D
2012-07-25 15:17:44 Ajey Golsangi
@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!!!
2011-10-22 08:10:46 Chandan Giri
define array globally!!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.