[UVA] 11718 - Fantasy of a Summation
|
I I U P C 2 0 0 9 |
||
|
|
||
|
Problem F: Fantasy of a Summation |
||
|
|
||
|
If you think codes, eat codes then sometimes you may get stressed. In your dreams you may see huge codes, as I have seen once. Here is the code I saw in my dream.
Actually the code was about - ‘You are given 3 integers n, K, MOD and n integers – A0, A1, A2, ... , An-1. You have to write K nested loops and calculate the summation of all Ai where i is the value of any nested loop variable.’
Now you have to find the result according to the code.
|
||
|
Input |
||
|
The first line of input contains T denoting the number of cases.
Each case starts with three integers – n ( 1 ≤ n ≤ 1000 ), K ( 1 ≤ K < 231 ), MOD ( 1 ≤ MOD ≤ 35000 ). The next line will contain n non-negative integers denoting A0, A1, A2, ... , An-1. Each of these integers will be fit into a 32 bit signed integer.
|
||
|
Output |
||
|
For each case print the case number and the result. Follow the sample output for the exact output format.
|
||
|
Sample Input |
Output for Sample Input |
|
|
2 3 1 35000 1 2 3 2 3 35000 1 2 |
Case 1: 6 Case 2: 36 |
|
|
|
||
|
Problem Setter: Jane Alam Jan Special Thanks: Anna Fariha |
||
對於單一個數字計算出現多少次, 首先設在哪一格出現, 因此有 k 種可能,
每一格有 n^(k-1) 種可能, 因此一個數字會出現 k*n^(k-1) 次,
把所有數字加起來之後乘上 k*n^(k-1) 就是答案。
#include <stdio.h>
long long mpow(long long x, long long y, long long mod) {
long long ret = 1;
while(y) {
if(y&1)
ret *= x, ret %= mod;
y >>= 1;
x = x*x, x %= mod;
}
return ret;
}
int main() {
int testcase, cases = 0;
int n, k, mod, i;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d", &n, &k, &mod);
long long sum = 0, x;
for(i = 0; i < n; i++)
scanf("%lld", &x), sum += x;
long long ret = (sum * mpow(n, k-1, mod) % mod * k)%mod;
printf("Case %d: %lld\n", ++cases, ret);
}
return 0;
}