Zigzag Sums Revised

Submit

Your name:
File:
Open code-statistics:

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

Define a sequence to be zigzag if no two adjacent terms are equal and no three consecutive terms are sorted ascending or descending. For example, (2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5) and (3, 1, 4, 1, 5) are zigzag sequences.

Let f(n) = the number of zigzag sequences of positive integers whose sum is n.

Print f(n) mod 10^7 for n = 1 to 97.

-- mitchs

Options

exec is denied

no deadline, the server will not save your submission

Sample input:_

*NOTHING*

Sample output:

1
1
3
4
7
12
19
29
48
75
118
186
293
460
725
1139
1789
2814
4422
6949
10924
17168
26979
42404
66644
104737
164610
258707
406588
639009
1004287
1578363
2480606
3898599
6127152
9629623
5134213
3785388
7381849
8750468
2334036
5115015
8067230
8437473
3331373
5348943
1441657
6832568
6893436
1527585
9207145
1899473
8540207
4803742
2784787
9136102
9389901
7770232
8585566
7395573
9197965
6584001
1276484
456649
7749629
903294
631615
6795255
6196260
796922
3697965
2338042
5845334
3332552
1247817
9942808
8318230
3201120
3339538
8427184
2992638
4163758
1856821
2898639
205082
9340234
824199
2963256
5826387
7436035
3255463
5074425
9957190
3995712
8595356
9909238
7233271

Ranking

Ruby _

RankUserSizeTimeDateStatistics
1mitchs1250.72772015/12/24 04:53:400B / 57B / 64B
2mitchs (alt)1370.05352015/12/25 11:18:590B / 60B / 69B

Perl _

RankUserSizeTimeDateStatistics
1tails1220.19892015/12/26 00:27:070B / 40B / 82B

Python _

RankUserSizeTimeDateStatistics
1mitchs1470.59532015/12/25 13:10:160B / 69B / 77B
2mitchs (alt)1600.12822015/12/25 11:04:170B / 78B / 73B
3rolf2100.32242015/12/24 04:34:370B / 112B / 70B

C++ _

RankUserSizeTimeDateStatistics
1nagibator20052860.01072016/05/17 18:55:490B / ?B / ?B

Haskell _

RankUserSizeTimeDateStatistics
1henkma1260.03342016/05/29 06:08:500B / 67B / 57B
2nagibator20051700.04162016/06/03 23:53:260B / ?B / ?B

R _

RankUserSizeTimeDateStatistics
1seichung1290.35562016/03/19 00:59:090B / ?B / ?B

Brainfuck _

RankUserSizeTimeDateStatistics
1mitchs (cheat)4160.03252016/07/13 12:59:43100B / 155B / 146B

GolfScript _

RankUserSizeTimeDateStatistics
1tails911.84672016/01/01 03:45:130B / 22B / 68B

Language Ranking_

RankLangUserSizeScore
1GolfScripttails9110000
2Perltails1227459
3Rubymitchs1257280
4Haskellhenkma1267222
5Rseichung1297054
6Pythonmitchs1476190
7C++nagibator20052863181
8Brainfuckmitchs (cheat)4162187

return top