TopCoder Statistics - Problem Statement

Problem Statement

Wolf Sothe is playing the game Delaymaster. In this game, he can create new words according to the following rules:

For each positive integer n, the string which consists of n copies of 'w' followed by n copies of 'o' is a valid word.
The concatenation of two valid words is a valid word.
Only the words that can be obtained by rules 1 and 2 are valid. There are no other valid words.

Thus, for example:

By rule 1, "wo", "wwoo", and "wwwwwooooo" are valid words.
Then, by rule 2, "wowwoo" is a valid word.
By applying rule 2 twice, "wowwoowo" is a valid word.
The strings "w", "ow", "woow", and "wwwoo" are not valid words.

Sothe has a very long string s. Each character of s is one of 'w', 'o', and '?'. Sothe wants to replace each '?' with either 'w' or 'o' in such a way that the result is a valid word. Return the number of different valid words he can obtain this way, modulo 1,000,000,007.

As s can be very long, you will have to generate it in your program. You are given nine ints: N, wlen, w0, wmul, wadd, olen, o0, omul, and oadd. Use the following pseudocode to generate s:

s = "???...???";				// Concatenation of N '?'s

signed_64bit_integer x = w0;
for(i=0;i&lt;wlen;i++){
	s[x] = 'w';				// Rewrite the x-th (0-based) character of s
	x = (x * wmul + wadd) % N;
}

x = o0;
for(i=0;i&lt;olen;i++){
	s[x] = 'o';				// Rewrite the x-th (0-based) character of s
	x = (x * omul + oadd) % N;
}

Definition

Class:: WolfDelaymasterHard
Method:: countWords
Parameters:: int, int, int, int, int, int, int, int, int
Returns:: int
Method signature:: int countWords(int N, int wlen, int w0, int wmul, int wadd, int olen, int o0, int omul, int oadd)
(be sure your method is public)

Constraints

N will be an even number between 2 and 2,000,000, inclusive.
wlen and olen will be between 0 and N, inclusive.
w0, wmul, wadd, o0, omul, and oadd will be between 0 and N - 1, inclusive.

Examples

2

1

0

0

1

0

1

0

1

Returns: 1
4

4

3

2

1

2

3

0

2

Returns: 1
6

1

4

2

3

6

1

3

0

Returns: 1
8

5

2

3

2

0

6

7

1

Returns: 6

s is "w?w?????". He can obtain six valid words: "wwwwoooo", "wwwooowo", "wowwwooo", "wowwoowo", "wowowwoo", and "wowowowo".
10

8

6

6

0

4

9

3

6

Returns: 2

s is "?o?o?ow??o".
12

1

7

4

3

6

1

11

8

Returns: 11

s is "?o?????o????".
14

11

1

11

4

3

11

0

12

Returns: 8
16

0

12

3

2

4

2

6

9

Returns: 8
18

6

4

9

2

9

17

14

10

Returns: 16
20

11

8

16

0

2

1

13

14

Returns: 128

s is "?o?????ow???????????".
200

111

164

135

103

76

14

178

57

Returns: 487696683
2000

766

391

1851

1494

1916

192

1078

1768

Returns: 421419494
20000

9193

7582

16803

19483

15614

15131

10189

8934

Returns: 885534941
200000

121974

105388

36129

136133

53995

33384

7397

170999

Returns: 236671729
2000000

1207830

1527272

1385106

279961

1416528

1583538

903038

677314

Returns: 329004958
2000000

951233

1953282

1692394

1046235

1080233

287350

686758

489004

Returns: 685943943
2000000

533847

1113200

639789

1234233

1542030

1056349

129675

335033

Returns: 722933011
2000000

1760904

327535

1549758

137278

1700088

1452755

1051335

1079265

Returns: 337487172
2000000

675394

1116936

813176

925803

242294

1267254

190454

1904537

Returns: 757017548
2000000

61574

1701259

845767

1749621

1254752

582618

1267432

330118

Returns: 218224895
2000000

1122821

1820064

1841253

781691

247127

741051

795931

315305

Returns: 180162747
2000000

444184

185751

1096715

1245912

801087

707748

1820677

171069

Returns: 894466281
2000000

1820395

424786

1098079

1611472

695883

1134259

1520045

73420

Returns: 700041541
2000000

1615462

1057034

8830

1556594

1001119

587100

1420903

575202

Returns: 884024211
2000000

635361

128420

70694

978360

983072

1844959

278905

427879

Returns: 754550627
2000000

0

50513

843746

507350

0

459231

641434

40549

Returns: 617521033
2000000

1095311

862878

1347500

1576961

0

324240

1432945

564499

Returns: 631721907
2000000

1115555

1164344

1936770

1037380

0

1232867

1669651

384310

Returns: 716159591
2000000

1487080

1359887

1961278

594822

0

1293571

796900

1201815

Returns: 315648473
2000000

485850

1799694

1561914

1521680

0

1813966

34049

825575

Returns: 50631202
2000000

580972

1771168

431794

1418525

0

1195211

713515

1011943

Returns: 378024255
2000000

0

1953895

305577

956411

332534

96732

970570

37318

Returns: 44153134
2000000

0

1325300

1974293

484496

769029

314925

1785327

287380

Returns: 584271953
2000000

0

202731

1202083

1487339

145032

849626

845964

1103697

Returns: 965415595
2000000

0

686359

1077718

1231556

1868982

725994

122190

1646416

Returns: 473430889
2000000

0

351399

65780

516075

1790125

1724060

153644

197891

Returns: 900458336
100

100

20

71

98

31

92

1

99

Returns: 2
2000000

1000000

0

1

1

0

0

0

0

Returns: 1
2000000

0

0

0

0

1000000

1000000

1

1

Returns: 1
2000000

250000

250000

1

2

0

0

0

0

Returns: 984940081
2000000

0

0

0

0

250000

1250000

1

2

Returns: 13066031
2000000

2000000

0

1

1

0

0

0

0

Returns: 0
2000000

0

0

0

0

2000000

0

1

1

Returns: 0
2000000

0

0

0

0

0

0

0

0

Returns: 617521033
2000000

1000000

0

1

2

500000

1250000

1

1

Returns: 2
2000000

500000

250000

1

1

1000000

1

1

2

Returns: 1
1834500

447

1834390

1

2

1750536

39324

1

0

Returns: 787968621
419904

321

419848

1

2

419716

1005

1

0

Returns: 586183501
1672658

772984

1670022

1

2

26465

3

1

0

Returns: 796270636
10

6

3

9

5

7

6

7

3

Returns: 1
20

19

12

9

15

1

8

11

1

Returns: 26

s is "??ww????o???ww??????".
30

19

4

13

11

7

21

21

5

Returns: 4
40

24

34

5

11

33

35

23

27

Returns: 296

s is "?w?o??w????w????o????w????w????wo?wow???".
50

16

1

35

1

38

15

5

31

Returns: 371416
60

35

8

55

3

11

20

9

29

Returns: 10058904

s is "????????w???????????o??w?????o????????????????????o????????o".
70

58

35

17

59

16

38

35

61

Returns: 336265
80

34

68

33

67

42

69

77

11

Returns: 192
90

79

22

81

85

57

4

85

51

Returns: 841573295
100

75

60

39

73

34

72

89

25

Returns: 480418909
2000

183

994

862

468

148

433

1247

1989

Returns: 532199331
2000000

1124789

474305

789443

1755525

1456142

1864782

1194875

1712395

Returns: 789625879
2000000

1684328

1892855

68543

1136077

1019166

351605

678595

671895

Returns: 283577435
2000000

312176

1180198

1238557

7723

1390030

1657892

1020285

1300163

Returns: 669457013
2000000

1850216

659549

243055

735595

1537638

1423528

1970895

534015

Returns: 852201575
2000000

1445999

1992745

1873653

1449027

826158

1041439

1744799

364445

Returns: 998843382
2000000

410670

493088

449457

1035315

479687

1729679

992237

1998281

Returns: 30223430
2000000

419443

1305303

1761823

1007025

874640

1516339

229519

1473199

Returns: 861766906
2000000

1720998

1316592

379363

563203

1836263

760099

1046895

1965633

Returns: 22668294
2000000

942360

1560206

1069783

622079

305064

1310599

292367

789433

Returns: 368937215
2000000

697610

1224484

443629

322891

520870

360785

1605759

1199517

Returns: 889702460
1999990

1999706

6

1

0

820028

1999545

1

2

Returns: 629111601
774340

16360

39863

1

0

210719

774109

1

2

Returns: 863961340
1999690

1999666

1999297

1

0

57684

1952877

1

2

Returns: 268974495
8

6

0

1

1

3

3

6

1

Returns: 0

s is "wwwoww??". He can't obtain any valid words.
2000000

1940508

1945440

469448

1465

638965

1876667

1421470

1365801

Returns: 388046247
2000000

769245

588689

1754842

1705143

1393262

205684

555585

894353

Returns: 0
2000000

1369720

207601

346059

631822

80497

1759150

1209992

1661058

Returns: 593252374
2000000

1685185

269621

322540

1996043

1165287

1959726

1196424

1170667

Returns: 124953695
2000000

1008275

1649063

233950

488117

1873836

943179

1299252

1354478

Returns: 532896330
2000000

1777614

1244328

364199

1118462

1925102

1428720

1749426

1743788

Returns: 756769470
2000000

984706

137433

1669555

732367

1986662

1567630

1540405

109277

Returns: 600611685
2000000

103352

1995294

865595

1517729

234780

1033556

432203

238089

Returns: 0
2000000

807269

949937

1320253

486311

890811

174942

706779

956809

Returns: 223487714
2000000

328286

54106

1430155

512458

438380

854206

1215919

177801

Returns: 687250304

Statistics

Problem Statement for "WolfDelaymasterHard"

Problem Statement

Definition

Constraints

Examples