Solving the Recurrence

Question

I am given F(0)=X and F(i)=(A⋅F(i−1)^2 + B⋅F(i−1) + C)%1000000 for 1≤i≤N.

Now given N,A,B,C and X, how to find all N elements effectively?

I need to divide these N elements in 2 sets where largest element goes in 1st set ,2nd largest in 2nd set , 3rd largest in 1st set and so on...and at the end need to find absolute differnece of the sum of elements of both the sets.

Can i find this difference without computing all elements as N can be as large as 10^7 and A,B,C,X are upto at max 100.

Answer 1

Note that the next element of the sequence depends only on the previous one, and there are no more than M=1000000 different elements since each result is an integer taken modulo 1000000. Thus the sequence is periodic from some point. You can generate the first few elements (no more than M) until you find the period, and then immediately know how many of each element there are if the total number of elements is N.

Now, 10^6 is at least some improvement when compared to 10^7. And once you know for each number from 0 to 999999 how many times it occurs in the sequence, you can find the required difference in O(M) operations, too.