# Google Kick Start 2019 – Practice Round – Kickstart Alarm Solution ### Problem :

Shil has a very hard time waking up in the morning each day, so he decides to buy a powerful alarm clock to Kickstart his day. This Alarm is called a Kickstart Alarm. It comes pre-configured with K powerful wakeup calls. Before going to bed, the user programs the clock with a Parameter Array consisting of the values A1A2, …, AN. In the morning, the clock will ring K times, with the i-th wakeup call having power POWERi.

To calculate POWERi, the alarm generates all the contiguous subarrays of the Parameter Array and calculates the summation of the i-th exponential-power of all contiguous subarrays. The i-th exponential-power of subarray AjAj+1, …, Ak is defined as Aj × 1i + Aj+1 × 2i + Aj+2 × 3i + … + Ak × (k-j+1)i. So POWERi is just the summation of the i-th exponential-power of all the contiguous subarrays of the Parameter Array.

For example, if i = 2, and A = [1, 4, 2], then the i-th exponential-power of A would be calculated as follows:

• 2-nd exponential-power of ` = 1 × 12 = 1`
• 2-nd exponential-power of ` = 4 × 12 = 4`
• 2-nd exponential-power of ` = 2 × 12 = 2`
• 2-nd exponential-power of `[1, 4] = 1 × 12 + 4 × 22 = 17`
• 2-nd exponential-power of `[4, 2] = 4 × 12 + 2 × 22 = 12`
• 2-nd exponential-power of `[1, 4, 2] = 1 × 12 + 4 × 22 + 2 × 32 = 35`

so the total is 71.

Tonight, Shil is using his Kickstart Alarm for the first time. Therefore, he is quite worried about the sound the alarm might make in the morning. It may wake up the neighbors, or, worse yet, it may wake up the whole planet! However, calculating the power of each wakeup call is quite difficult for him. Given K and the Parameter Array A1A2, …, AN, can you help him by calculating the summation of power of each wakeup call: POWER1 + POWER2 + … + POWERK?

Input :

The first line of the input gives the number of test cases, TT test cases follow. Each test case consists of one line with nine integers N, K, x1, y1, C, D, E1, E2 and FN is the length of array AK is the number of wakeup calls. Rest of the values are parameters that you should use to generate the elements of the array A, as follows.

Use the recurrences below to generate xi and yi for i = 2 to N:

• xi = ( C × xi-1 + D × yi-1 + E1 ) modulo F.
• yi = ( D × xi-1 + C × yi-1 + E2 ) modulo F.

We define Ai = ( xi + yi ) modulo F, for all i = 1 to N.

Output :

For each test case, output one line containing `Case #x: POWER`, where `x` is the test case number (starting from 1) and `POWER` is the summation of POWERi, for i = 1 to K. Since `POWER` could be huge, print it modulo 1000000007 (109 + 7).

Limits :

1 ≤ T ≤ 100.
Time limit: 90 seconds per test set.
Memory limit: 1 GB.
`1 ≤ x1 ≤ 105.1 ≤ y1 ≤ 1051 ≤ C ≤ 105.1 ≤ D ≤ 105.1 ≤ E1 ≤ 105.1 ≤ E2 ≤ 105.1 ≤ F ≤ 105.`

Small dataset (Test set 1 – Visible) :

`1 ≤ N ≤ 100.1 ≤ K ≤ 20`.

Large dataset (Test set 2 – Hidden) :

`1 ≤ N ≤ 106.1 ≤ K ≤ 104`.

Sample :

In Sample Case #1, the Parameter Array is [3, 2]. All the contiguous subarrays are , , [3, 2].

For i = 1:

• 1-st Exponential-power of  = 3 × 11 = 3
• 1-st Exponential-power of  = 2 × 11 = 2
• 1-st Exponential-power of [3, 2] = 3 + 2 × 21 = 7

So POWER1 is 12.

For i = 2:

• 2-nd Exponential-power of  = 3 × 12 = 3
• 2-nd Exponential-power of  = 2 × 12 = 2
• 2-nd Exponential-power of [3, 2] = 3 + 2 × 22 = 11

So POWER2 is 16.

For i = 3:

• 3-rd Exponential-power of  = 3 × 13 = 3
• 3-rd Exponential-power of  = 2 × 13 = 2
• 3-rd Exponential-power of [3, 2] = 3 + 2 × 23 = 19

So POWER3 is 24.

### Solution :

``````#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = pow(10,9)+7;
ll getPow(ll a,ll p){
ll ret = 1,cp = a;
while(p){
if(p&1) ret = (ret*cp)%MOD;
p >>= 1;
cp = (cp*cp)%MOD;
}
return ret;
}
ll getK(ll i,ll k){
if(i == 1) return k%MOD;
ll ret = ((i*(getPow(i,k)-1)%MOD)*getPow(i-1,MOD-2))%MOD;
return ret;
}
int main(){
int T;
cin >> T;
for(int k = 1; k <= T; ++k){
ll N,K,x1,y1,C,D,E1,E2,F;
cin >> N >> K >> x1 >> y1 >> C >> D >> E1 >> E2 >> F;
vector<ll> A(N);
A = (x1+y1)%F;
ll CD = C+D,E = E1+E2;
for(ll i = 1; i < N; ++i) A[i] = (CD*A[i-1]+E)%F;
ll psum = 0,nb = 1,kval = N,ret = 0;
for(ll i = N-1; i >= 0; --i){
psum = (psum+nb*A[i])%MOD;
++nb;
ret = (ret+psum*getK(kval,K))%MOD;
--kval;
}
cout << "Case #" << k << ": " << ret << "\n";
}
return 0;
}``````

403 total views,  2 views today