[UVA][組合] 12028 - A Gift from the Setter
Problem setting is somewhat of a cruel task of throwing something at the contestants and having them scratch their head to derive a solution. In this problem, the setter is a bit kind and has decided to gift the contestants an algorithm which they should code and submit. The C/C++ equivalent code of the algorithm is given below:
![framebox{
parbox{5.5in}{
texttt{ \
long long GetDiffSum( int a[], int n ) ...
...extit{abs means absolute value} \
mbox{ } return sum; \
} \
}
}
}](http://uva.onlinejudge.org/external/120/12028img1.png)
The values of array a[] are generated by the following recurrence relation:
long long GetDiffSum( int a[], int n )
But the setter soon realizes that the straight forward implementation of the code is not efficient
enough and may return the famous ``TLE" and that's why he asks you to optimize the code.
Input
Input starts with an integer T (
100), denoting the number of test cases.
Each case contains four integers K, C, n and a[0]. You can assume that (
1K, C,
a[0]104) and
(
2n105).
Output
For each case, print the case number and the value returned by the function as stated above.
Sample Input
2 1 1 2 1 10 10 10 5
Sample Output
Case 1: 1 Case 2: 7136758
由於 n 不大，先把表建出來。
接著將其排序，讓 abs() 的效用去除，接著使用數學組合去計算。
計算的方式是，計算相鄰兩個數字的差，而這個差會被使用幾次？
使用次數：左邊的個數乘上右邊的個數
又或者(我沒測過)對於一個數字放在後面的這些加總為何 (an - ai) + (an-1 - ai) ... +(ai-ai)
= sigma(an...ai) - (n-i+1)*ai
#include <stdio.h>
#include <algorithm>
using namespace std;
long long a[100000];
int main() {
int testcase, cases = 0;
int K, C, n, i;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d %lld", &K, &C, &n, &a[0]);
for(i = 1; i < n; i++)
a[i] = (K*a[i-1]+C)%1000007;
sort(a, a+n);
long long ret = 0;
for(i = 1; i < n; i++)
ret += (a[i]-a[i-1])*(n-i)*i;
printf("Case %d: %lld\n", ++cases, ret);
}
return 0;
}