StringsNightmareAgain

SRM 621 · 2013-12-22 · by rng_58

SRM 621 · 2013-12-22 · by rng_58 · String Manipulation

Show categories

Class Name: StringsNightmareAgain

Return Type: long

Method Name: UniqueSubstrings

Arg Types: (int, int, int, int, int)

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';
}

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

12)

2
3
1
1
6
Returns: 3

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

23)

4
3
1
1
6
Returns: 3

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

34)

4
3
3
3
10
Returns: 5

The input string is "babbaaaaab".

45)

5
3
2
3
11
Returns: 9

The input string is "abbaabaaabb".

56)

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

Submissions are judged against all 108 archived test cases, of which 10 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StringsNightmareAgain with a public method long long UniqueSubstrings(int a, int b, int c, int d, int n) · 108 test cases · 2 s / 256 MB per case