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
Input: 2 1 0 0 3 3 1 2 6 Output: 3 103
hide comments
|
nikhil0010:
2022-04-29 08:23:41
Bullshit time limit , giving TLE even in nlogn |
|
sinhadipti:
2021-04-06 04:56:27
Nice problem, learned the "Running Median of an input Stream" algorithm with min and max heap. |
|
jayss5:
2020-06-18 23:57:05
Ac in one go !!!! |
|
sarthak_19:
2020-06-03 09:07:16
My 100th on Spoj
|
|
hemansh_31:
2020-05-11 20:41:52
quite similar to the running median problem 2 |
|
vidhan_1234:
2020-04-24 11:39:16
TLE in java....
|
|
kiran577:
2020-04-23 19:10:52
Any one got AC using JAVA,even after using priority queue's with fast reader and StringBuffer for output i'm still getting TLE. |
|
shubham_04_04:
2019-12-06 03:17:03
Getting tle even after using two priority queue and fast reading in java |
|
maneeshkrpatel:
2019-11-23 22:43:43
Very strict time limit..
|
|
roopammishra:
2019-11-01 01:59:26
Don't take modulo of F[1]+F[2]+...+F[n]...Got 1 WA :( |
| 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 |
RSS