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
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
Harpreet Singh: 2014-12-04 18:26:36

strict^strict timelimit

Kunal Behl: 2014-09-13 15:53:45

y time limit exceed everytime?? can anybody help please..

Matija Martiniæ: 2014-06-04 21:24:16

TLE even after using stl heap c++... :(
what to do now..??

(Tjandra Satria Gunawan)(曾毅昆): 2014-02-02 23:17:12

Time limit is too strict!

SaSukE: 2013-05-17 12:42:45

why implementation using red black tree is giving TLE ?? :/....Insertion and every query takes O(logn) still getting TLE ?? What should be the complexity of the solutn ??

Last edit: 2013-05-17 12:56:55
J.A.R.V.I.S.: 2013-02-03 13:36:52

Nice one :) solvable with STLs.. Watch out for overflows...

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