UVa 11718 - Fantasy of a Summation

 Link: https://uva.onlinejudge.org/external/117/11718.pdf


/*
    Accepted

    sum = ( A[0] + A[1] + A[2] + ... + A[k] ) % M

    ans = (sum * N ^ (K-1) * K) % M
                 ---------
                 Big Mod

    [N:B: Use Big Mod to avoid TLE]

*/

#include<bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define psb push_back
#define fast ios_base::sync_with_stdio(false)

typedef map<string, int>mpsi;
typedef map<int, string>mpis;
typedef long long LL;

const int high = 1005;
const int inf = (1 << 31) - 1;

LL get_power(int N, int K, int M)
{


    LL x = 1;

    if(K == 0) return 1;

    x = get_power(N , K/2, M);

    if(K%2==0)
    {
        return x = ((x % M) * (x % M)) % M;
    }

    else
    {
        return x = ((N % M) * ((x % M) * (x % M))) % M;
    }
}

int main()
{
    fast;
    int i, test, tc=0 , x;
    int N, K , M;

    cin >> test;

    while(test--)
    {
        cin >> N >> K >> M;

        LL sum = 0;

        for(i=0; i<N; i++)
        {
            cin >> x;

            sum += x;
        }

        int res = ((sum % M) * get_power(N , K-1, M)) % M;

        int ans = (res * (K % M)) % M;

        cout << "Case " << ++tc << ": " << ans << "\n";
    }

    return 0;
}