TopCoder problem "StrangeArray" used in SRM 387 (Division I Level Three)



Problem Statement

    

You are given an infinite sequence P, where the i-th member is defined as follows: 

  P[i] = (A[i % A.size] ^ (B[i % B.size] + i / B.size)) % 1000000007

where % denotes modulo, ^ denotes exponentiation, / denotes integer division, and X.size represents the number of elements in X.

Alternatively, the following pseudocode can be used to calculate the elements of P successively: 

int i = 0;
loop forever
	P[i] = (A[i % A.size] ^ B[i % B.size]) % 1000000007;
	B[i % B.size] = B[i % B.size] + 1;
	i = i + 1;
end of loop

You are given int[]s A and B, and a String N containing an integer. Calculate the sum of the first N elements of the sequence (i.e., P[0] + P[1] + ... + P[N - 1]), and return that sum modulo 1000000007.

 

Definition

    
Class:StrangeArray
Method:calculateSum
Parameters:int[], int[], String
Returns:int
Method signature:int calculateSum(int[] A, int[] B, String N)
(be sure your method is public)
    
 

Constraints

-A and B will each contain between 1 and 50 elements, inclusive.
-Each element of A and B will be between 1 and 10^9, inclusive.
-N will represent an integer between 1 and 10^18, inclusive, with no leading zeros.
 

Examples

0)
    
{1,2,3}
{3,4}
"2"
Returns: 17
1^3 + 2^4 = 17.
1)
    
{2, 3, 4}
{2, 3}
"3"
Returns: 95
2^2 + 3^3 + 4^(2 + 1) = 95.
2)
    
{2, 3, 4}
{2, 3}
"5"
Returns: 192
2^2 + 3^3 + 4^(2 + 1) + 2^(3 + 1) + 3^(2 + 2) = 192.
3)
    
{1, 2, 3, 4}
{1}
"1000000000"
Returns: 607570807
1^1 + 2^2 + 3^3 + 4^4 + 1^5 + 2^6 + ... + 4^1000000000 = 607570807 (mod 1000000007).

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11121&pm=8086

Writer:

Relja

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Math, Recursion