WEIRDFN - Weird Function
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].
Input
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
Output T lines, one for each test case, containing the required sum.
Constraints
1 <= T <= 100
0 <= a, b, c < 1000000007
1 <= n <= 200000
Example
Sample Input:
2 1 0 0 3 3 1 2 6
Sample Output:
3 103
hide comments
n_k_rathi:
2016-06-21 07:27:00
Hi,
|
|
5e9f0u1t:
2015-12-14 21:02:05
bad question..try optimising number of modulo operations
|
|
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++... :(
|
|
(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 ??
|
|
J.A.R.V.I.S.:
2013-02-03 13:36:52
Nice one :) solvable with STLs.. Watch out for overflows... |
|
conioh:
2013-01-27 12:20:48
nice question... |
|
Nilendu Das:
2012-12-09 20:07:18
Good question.. You can take help from RRATING problem from codechef..Jst the partition is diff.. |
Added by: | Varun Jalan |
Date: | 2010-01-25 |
Time limit: | 1.116s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | own problem used for Codechef Snackdown Onsite |