Problem statement:
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
Output T lines, one for each test case, containing the required sum.
2
1 0 0 3
3 1 2 6
Sample Output :
3
103
Constraints
1 <= T <= 100
0 <= a,b,c < 1000000007
1 <= n <= 200000
Code in C++:
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
Example
Sample Input :2
1 0 0 3
3 1 2 6
Sample Output :
3
103
Constraints
0 <= a,b,c < 1000000007
1 <= n <= 200000
Code in C++:
No comments:
Post a Comment