StrangeArray

SRM 387 · 2008-01-09 · by Relja

SRM 387 · 2008-01-09 · by Relja · Math, Recursion

Show categories

Class Name: StrangeArray

Return Type: int

Method Name: calculateSum

Arg Types: (vector<int>, vector<int>, string)

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.

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

{1,2,3}
{3,4}
"2"
Returns: 17

1^3 + 2^4 = 17.

{382641071,105868709,565477462,20966216,485030671,100680562,231543931,401104770,219153416,245277260,844752342,157048249,955992309,648030030,916287728,745689260,852565080,754020813,861415448,169896542,654683065,562944425,470595416,189642017}
{188360240,778649250,585924863,917783135,697714163,421491134,388866847,581835383,684072389,935087130,205572679,733207190,403942991,317972350,235969115,684743797,680990020,312540055,112949003,458082827,188970610,181249427,697958311,22217474,861445966,102420117,19013031,103946043,584795678,716208380,757866145,352214117,830713827,852198858,191625720}
"998168889431440168"
Returns: 467033071

{996520889,764213995,824060792,344279305,818536942,388164922,910580767,524002807,18311105,402081362,538804284,100009155,495925778,588671529,411877803,309244056,1983703,811700796,91341898,508529923,841547898,529709768,580828272,48738059,376415295,913510544,99124118,580675679,233008819,847926267,199011200,323526718,621295815,600268562,887813959,327890865,671193578,435377056}
{906552323,263924069,193090609,959715567,823145237,766136661,768333994,474806970,96591082,866237372,575762199,122104556,768089846,544816431,861384929,99765007,934995574,933896908,456373790,733115634,664815210,200628681,250373851,679830317,504501480,644154179,26154362,51149021,241798150,36500137,561662648,730521561,74709311,739158299,406079287,670308542,845759453,625629444,236030152,448805200,496353038,342631305}
"970091860713522751"
Returns: 464368420

{940031128,142277291,873012482,720755638,401135288,159123508,576952421,480117191,104861598,315256202,668019653,444563127,750541703,5279702,984344004,533707693,777092806,819269386,535538804,879268776,807367168,334269234,752891628,199652088,149388103,736259041,249122592,645496993,885250404,677877132,869411297}
{771660512,579210791,279213843,314401684,792870876,136295663,677297280,117099520,778710287,842493972,30396435,254188665,944242683,117587817,384105960,173467207,692495498,12665181,304574724,518692587,565446943,982482375,685903500,332712790,759147923,964690084,637348551,20599993,359752189,297006134,857112338,853602710,956389049,503585924,398419141,295388653,787316507,481429486}
"398724326303903317"
Returns: 77251250

{118778038,529892880,286233100,709799493,876430555,19318216,298501541,928403576,362712485,409527878,754417554,159947508,434644611,200476088,441267128,679738761,854915005,839045381,314279610,235999633,37171544,607806634,453505050,303750724,910702841,157353434,93508713,121311075,434766685,86642048,506149479,166539506,795373393,478957487,18311105,228797265,814325388,798913541,945616016,732810449,602832117,57100131,723410748}
{470595416,990325632,648792992,16296884,398144474,759758293,772148808,87343974,652485732,221228675,833552049,208410901,445905941,154271065,744743186,392651142,993408001,650898770,519333475,230506302,129306924,890011291,74159978,110782189,770104068,374919888,641987365,607226783,878505813,664906765,701773125,312662129,86519974,132114627,832758568,901791436,632435071,775231177,398876918,703421124}
"75472273934141056"
Returns: 884628318

51)

{2, 3, 4}
{2, 3}
"3"
Returns: 95

2^2 + 3^3 + 4^(2 + 1) = 95.

52)

{2, 3, 4}
{2, 3}
"5"
Returns: 192

2^2 + 3^3 + 4^(2 + 1) + 2^(3 + 1) + 3^(2 + 2) = 192.

53)

{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).

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

Coding Area

Language: C++17 · define a public class StrangeArray with a public method int calculateSum(vector<int> A, vector<int> B, string N) · 67 test cases · 2 s / 256 MB per case