StringsNightmareAgain | Topcoder Archive

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".
```
2
```
```
3
```
```
1
```
```
1
```
```
6
```
```
Returns: 3
```
The input string is "aaaabb". It is the example in the statement.
```
4
```
```
3
```
```
1
```
```
1
```
```
6
```
```
Returns: 3
```
The input string is "bbaabb". The answer is 3. The magical substrings are "a", "b" and "bb".
```
4
```
```
3
```
```
3
```
```
3
```
```
10
```
```
Returns: 5
```
The input string is "babbaaaaab".
```
5
```
```
3
```
```
2
```
```
3
```
```
11
```
```
Returns: 9
```
The input string is "abbaabaaabb".
```
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".

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.