lniniaa
BAN USERIt must be something like this:
mul=1;
add=0;
swap=false;
swap_ptr=0;
for i from 0 to n-1
{
if (op==A) {add+=X;}
if (op==M) {mul*=Y; add*=Y;}
if (op==R) {
swap (array[i], array[n-1]);
swap=true;
array[i]=(array[i]*mul+add) mod Z;
swap_ptr=2;
continue;
}
if (swap==true)
if (i<n-swap_ptr)
swap (array[i], array[n-swap_ptr++]);
else {
swap==false;
}
array[i]=(array[i]*mul+add) mod Z;
}
The key is to realize A and M operations can be delayed until you need to calculate the final result. For example, the operation sequence AAMAM (X=1,Y=2) is equal to a single step calculation to the original item a which is: a*4+10. So in the ith operation, you only have to calculate the ith element's final value and update the single step calculation according to the ith operation.
And when the ith operation is R, what we should do is starting to swap the ith to nth elements one pair per operation (ith and nth, i+1th and n-1th) and apply the single step calculation to the new ith element and move on. If no new R, just keep swapping. When we encounter another R in position j. We should stop the previous swapping and begin a new one from jth to nth.
(a*b) mod Z = (a mod Z)*(b mod Z). The function can surely be refined.
- lniniaa January 05, 2014