WEIRDFN - Weird Function

no tags 

Let us define:

  • F[1] = 1
  • F[i] = (a*M[i] + b*i + c)%1000000007 for i > 1

where M[i] is the median of the array {F[1], F[2], ..., F[i-1]}.

The median of an array is the middle element of that array when it is sorted. If there are an even number of elements in the array, we choose the first of the middle two elements to be the median.

Given a, b, c and n, calculate the sum F[1] + F[2] + .. + F[n].


The first line contains T the number of test cases. Each of the next T lines contain 4 integers : a, b, c and n.


Output T lines, one for each test case, containing the required sum.


1 <= T <= 100
0 <= a, b, c < 1000000007
1 <= n <= 200000


Sample Input:

1 0 0 3
3 1 2 6

Sample Output:


hide comments
baddu609: 2019-05-29 22:50:26

Be careful, Take mod of terms only, not the mod for the final answer.

Aditya: 2019-04-18 20:54:52

The same solution got accepted in c++ but gave tle in Java.

Last edit: 2019-04-18 20:55:16
tanmay2904: 2019-03-24 20:53:50

@hp1999 bcoz clearing them using priority_queue.clear() takes O(n) time

hp1999: 2019-03-10 13:09:31

I can't get it. I got TLE when I declared the priority queues outside the 't' while loop (the one I used for test cases) and was emptying them after each iteration. But when I declared them inside it, I got AC. What could be the reason?

masterchef2209: 2019-01-17 11:38:02

LESSON LEARNED=priority_queue is faster than multiset
got AC by changing multiset impl. to priority_queue one

tan_sourabh: 2019-01-16 18:09:54

Nice problem, can be done using priority_queue. Choose priority_queue over set, if you are using STL.

taponidhi: 2018-05-21 12:57:32

It's a really gud question with nice STL implementation.Just remember to not take modulus of ∑F(i).If you take modulus,it will give wrong answer.I was kinda stuck there :( .

shahianshu: 2018-02-13 12:22:38

question can be solved in c++ by using priority queue stl by making two priority queue left and right and taking the middle as integer and forming logic based on the question.

n_k_rathi: 2016-06-21 07:27:00

I am not sure if I can meet the Time Limit in Java, it shouldn't be language agnostic.
is 1.116s enough for n=200000?

5e9f0u1t: 2015-12-14 21:02:05

bad question..try optimising number of modulo operations

Last edit: 2015-12-14 21:02:48

Added by:Varun Jalan
Time limit:1.116s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:own problem used for Codechef Snackdown Onsite