TopCoder problem "MultiReplacer" used in SRM 230 (Division I Level Three)



Problem Statement

    Let f be a function that takes a string composed of a's, b's, and c's, and replaces every occurrence of 'a' with arep, 'b' with brep, and 'c' with crep. Your code will compute the length of (quotes for clarity): 
	f( f( f( ... f(a) ... ) ) ) : f applied iter times to the string "a"
Since the lengths can grow very large with only a few iterations, you will return the length mod m. For example, if 
	arep = abc
	brep = c
	crep = ba
	iter = 3
	m = 7
then you will find the length of 
	f(f(f(a))) = f(f(abc)) = f(abccba) = abccbabacabc ,
which is 12. Then you will compute 12 mod 7 = 5, and return 5.
 

Definition

    
Class:MultiReplacer
Method:length
Parameters:String, String, String, int, int
Returns:long
Method signature:long length(String arep, String brep, String crep, int iter, int m)
(be sure your method is public)
    
 

Constraints

-arep, brep, and crep will contain between 1 and 50 characters inclusive.
-Each character in arep, brep, and crep will be 'a', 'b', or 'c'.
-iter will be between 1 and 2000000000 inclusive.
-m will be between 2 and 2^31-1 inclusive.
 

Examples

0)
    
"abc"
"c"
"ba"
3
7
Returns: 5
Same as above.
1)
    
"b"
"c"
"a"
2000000000
100
Returns: 1
2)
    
"b"
"c"
"aa"
30
10000
Returns: 1024
3)
    
"acabbcabbabac"
"cababcababcabcabacbacbabcacb"
"acbacbabcababcabababbabcbcab"
2000000000
2000000000
Returns: 1876480521

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3046

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6519&pm=3046

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , Olexiy

Problem categories:

Math