TopCoder Statistics - Problem Statement

Problem Statement

Bruce has been having lots of nightmares recently. In the nightmares an evil wizard always asks him string problems. Bruce is terrible in solving string problems. He needs your help with one problem he recently encountered in his dream.

There is a string S written on a wall. Each letter of the string is either 'a' or 'b'. Some substrings of S are magical. More precisely, a substring is magical if and only if it has two non-overlapping occurrences in S.

For instance, if S="aaaabb", the magical substrings are "a", "aa", and "b". Note that the substring "aaa" occurs twice but the two occurrences overlap. Hence, "aaa" is not a magical substring of this S.

You are given five ints: a, b, c, d, and n. Use them to generate the string S using the procedure described below. Then, compute and return the number of distinct magical substrings in S.

Use the following pseudocode to generate S:

S = "";
for (int i = 0; i &lt n; ++i)
{
	S.append('a');
}
for (int i = 0; i &lt a; ++i)
{
	b = (b*c+d)%n;
	S[b] = 'b';
}

Definition

Class:: StringsNightmareAgain
Method:: UniqueSubstrings
Parameters:: int, int, int, int, int
Returns:: long
Method signature:: long UniqueSubstrings(int a, int b, int c, int d, int n)
(be sure your method is public)

Notes

The pseudo-random generator has no special properties. We are only using it to keep the input small. There is a general solution that works for all possible strings with at most 100,000 characters.
Watch out for integer overflow. In particular, 32-bit integers may overflow when computing (b*c+d).

Constraints

n will be between 1 and 10^5, inclusive.
a, b, c and d will be between 0 and 10^6, inclusive.

Examples

0

0

0

0

4

Returns: 2

The input string is S="aaaa". There are two magical substrings: "a" and "aa".
8

10

18

12

1

Returns: 0
90000

0

90001

3

100000

Returns: 2986846
8

15

4

8

12

Returns: 13
3

8

4

4

11

Returns: 5
10

4

18

18

18

Returns: 8
6

9

11

14

19

Returns: 25
18

14

1

11

4

Returns: 2
6

3

20

16

16

Returns: 9
9

20

2

12

14

Returns: 14
5

4

9

14

11

Returns: 6
19

12

9

17

13

Returns: 7
2

3

1

1

6

Returns: 3

The input string is "aaaabb". It is the example in the statement.
3

2

12

2

13

Returns: 7
598

187

171

368

715

Returns: 2703
517

257

91

463

169

Returns: 154
839

713

160

651

884

Returns: 5063
882

421

312

517

994

Returns: 3845
781

799

550

342

132

Returns: 1154
28

73

237

502

927

Returns: 10786
402

427

663

350

777

Returns: 15476
717

130

142

457

151

Returns: 224
426

131

128

572

532

Returns: 3971
4

3

1

1

6

Returns: 3

The input string is "bbaabb". The answer is 3. The magical substrings are "a", "b" and "bb".
394

187

809

585

304

Returns: 2620
5455

1992

7462

8731

133

Returns: 413
1643

8770

3478

4547

900

Returns: 6637
2171

162

6732

4360

639

Returns: 6056
6730

6007

5811

6336

484

Returns: 19425
6083

9729

975

7420

826

Returns: 3155
7088

9449

9849

4243

755

Returns: 4379
7808

5284

7706

593

59

Returns: 64
29

2572

7070

4956

241

Returns: 526
5542

5987

3673

5989

552

Returns: 6030
4

3

3

3

10

Returns: 5

The input string is "babbaaaaab".
9505

8201

455

4199

176

Returns: 2999
1640

9348

69526

74534

93155

Returns: 2605483
10891

89442

41266

75454

60128

Returns: 3255247
73251

37081

81127

79595

30619

Returns: 111980
75840

29751

56136

56493

50650

Returns: 47208834
69336

27434

71291

15854

3951

Returns: 12801
31372

35999

98264

68029

5155

Returns: 18857
29308

37409

64199

54922

68920

Returns: 3124447
80775

96594

54760

29748

88938

Returns: 48175538
60845

58630

7732

79569

45855

Returns: 706985
5

3

2

3

11

Returns: 9

The input string is "abbaabaaabb".
68818

25690

90116

24091

8475

Returns: 1375908
38467

87543

88269

56705

150

Returns: 1493
73579

87037

73717

39593

36312

Returns: 144872371
44787

59605

56175

39130

42642

Returns: 2239550
14757

82632

44472

91102

13460

Returns: 165843
52563

89179

75842

29983

66277

Returns: 137854
48203

21785

83949

22817

91298

Returns: 1041072342
73481

91896

63262

62542

90580

Returns: 1351287
9536

58820

64137

99221

58043

Returns: 129820
79034

80676

89295

2112

43853

Returns: 78218
10

1000000

1000000

1

51

Returns: 63

Please, do not forget that the calculations may overflow if you use 32-bit integers. The input string is "aaaaaaaabbaaabbaaaaaaababaaaababaaaaaaaaaabaaaaaaab".
69916

9466

87966

27354

98180

Returns: 769636325
928288

705394

782425

799478

39546

Returns: 1538516
353255

702945

324160

690526

2351

Returns: 3550
724238

921995

396134

565562

13233

Returns: 106802
640327

821328

616771

437552

33888

Returns: 126023311
296869

616399

447537

584174

32921

Returns: 175644
120288

7431

230941

509338

36414

Returns: 12661950
62870

306096

559711

650678

20240

Returns: 1262660
428559

949176

785705

823246

27799

Returns: 11664
981743

985926

746744

325977

64193

Returns: 232643
9

10

11

11

2

Returns: 1
325069

434741

753696

356988

86044

Returns: 451875017
573955

854415

921421

706281

69736

Returns: 452310616
193338

643185

756261

280594

68534

Returns: 61292
512481

198274

299285

206998

61738

Returns: 53048
93301

910263

394591

609396

23080

Returns: 42455239
793671

360595

440429

143192

24172

Returns: 138381
430259

230767

164693

547393

17573

Returns: 24985
906849

794264

175216

588667

98451

Returns: 1076452227
427881

352381

20595

781456

96347

Returns: 4952791
892386

486832

606196

676887

90200

Returns: 471580551
17

3

13

8

9

Returns: 4
1000

0

90001

3

100000

Returns: 1561646
66047

0

90001

3

100000

Returns: 17876699
174

0

90001

3

100000

Returns: 5309264
98588

0

90001

3

100000

Returns: 1664762
63577

0

90001

3

100000

Returns: 9367883
50000

0

90001

3

100000

Returns: 2992126
50000

0

90001

3

100000

Returns: 2992126
50000

0

90001

3

100000

Returns: 2992126
50000

0

90001

3

100000

Returns: 2992126
50000

0

90001

3

100000

Returns: 2992126
0

16

7

18

13

Returns: 6
50000

0

90001

3

100000

Returns: 2992126
10000

0

90001

3

100000

Returns: 2986873
10000

0

90001

3

100000

Returns: 2986873
10000

0

90001

3

100000

Returns: 2986873
10000

0

90001

3

100000

Returns: 2986873
10000

0

90001

3

100000

Returns: 2986873
90000

0

90001

3

100000

Returns: 2986846
90000

0

90001

3

100000

Returns: 2986846
90000

0

90001

3

100000

Returns: 2986846
90000

0

90001

3

100000

Returns: 2986846
23743

34728

72847

72487

100000

Returns: 697380999
50000

3

5

2

100000

Returns: 262167577
224678

567854

135478

445689

100000

Returns: 3958740
50000

345234

234

23423

100000

Returns: 22715679
454167

446237

546815

544121

94501

Returns: 36581029
1009

1007

1011

1013

100000

Returns: 2111280
1000000

1000000

1000000

1000000

100000

Returns: 49999
0

0

0

0

100000

Returns: 50000

Statistics

Problem Statement for "StringsNightmareAgain"

Problem Statement

Definition

Notes

Constraints

Examples