WolfDelaymasterHard

SRM 593 · 2013-06-25 · by rng_58

SRM 593 · 2013-06-25 · by rng_58 · Dynamic Programming

Show categories

Class Name: WolfDelaymasterHard

Return Type: int

Method Name: countWords

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

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<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<olen;i++){
	s[x] = 'o';				// Rewrite the x-th (0-based) character of s
	x = (x * omul + oadd) % N;
}

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

20
11
8
16
0
2
1
13
14
Returns: 128

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

50)

20
19
12
9
15
1
8
11
1
Returns: 26

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

52)

40
24
34
5
11
33
35
23
27
Returns: 296

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

54)

60
35
8
55
3
11
20
9
29
Returns: 10058904

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

73)

8
6
0
1
1
3
3
6
1
Returns: 0

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

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

Coding Area

Language: C++17 · define a public class WolfDelaymasterHard with a public method int countWords(int N, int wlen, int w0, int wmul, int wadd, int olen, int o0, int omul, int oadd) · 84 test cases · 2 s / 256 MB per case