Soluție HackerRank pentru Manasa and Pizza, subdomeniul Algebra, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Manasa and Pizza
- Domeniu: Algebra
- Limbaj: C++14
Challenge: Manasa and Pizza
Subdomeniu: Algebra (algebra)
Scor cont: 80.0 / 80
Submission status: Accepted
Submission score: 1.0
Submission ID: 464735236
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/manasa-and-pizza/problem
Cerință
With the college fest approaching soon, Manasa is following a strict dieting regime . Today, she just cannot resist her temptation for having a pizza. An inner conflict ensues, and she decides that she will have a pizza, only if she comes up with a solution to the problem stated below. Help her get the pizza for herself.
Given a list L of N numbers, where
_L = { a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, a<sub>4</sub> .... , a<sub>N</sub>}_
Find the value of M that is computed as described below.
Input Format
The first line contains an integer N i.e. size of the list L.
The next line contains N space separated integers, each representing an element of the list L.
Output Format
Print the value of M _modulo (10<sup>9</sup> + 7)_.
Constraints
1 ≤ N ≤ 5100
0 ≤ _a<sub>i</sub>_ ≤ 10<sup>15</sup> , where _i ∈ [1 .. N]_
Sample Input 00
3
1 2 3
Sample Output 00
40392
Explanation
There are 8 subsets of given set,
1. S = {1,2,3} and L - S ={0} value of F(6) = 19601
2. S = {1,2} and L - S ={3} value of F(0) = 1
3. S = {1,3} and L - S ={2} value of F(2) = 17
4. S = {2,3} and L - S ={1} value of F(4) = 577
5. S = {1} and L - S ={2,3} value of F(4) = 577
6. S = {2} and L - S ={1,3} value of F(2) = 17
7. S = {3} and L - S ={1,2} value of F(0) = 1
8. S = {} and L - S ={1,2,3} value of F(6) = 19601
Adding all these values, we get M = 40392.
Cod sursă
//manasa-and-pizza.cpp
//Manasa and Pizza
//Ad Infinitum - Math Programming Contest June'14
//Author: derekhh
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 3, MOD = 1000000007;
struct Matrix
{
int v[MAXN][MAXN], row, col;
};
Matrix add(Matrix a, Matrix b)
{
Matrix ans;
ans.row = a.row, ans.col = a.col;
for (int i = 1; i <= a.row; i++)
for (int j = 1; j <= a.col; j++)
ans.v[i][j] = (a.v[i][j] + b.v[i][j]) % MOD;
return ans;
}
Matrix mul(Matrix a, Matrix b)
{
Matrix ans;
ans.row = a.row, ans.col = b.col;
for (int i = 1; i <= a.row; i++)
{
for (int j = 1; j <= b.col; j++)
{
ans.v[i][j] = 0;
for (int k = 1; k <= a.col; k++)
ans.v[i][j] = (ans.v[i][j] + (long long)a.v[i][k] * b.v[k][j]) % MOD;
}
}
return ans;
}
Matrix power(Matrix a, long long n)
{
Matrix res;
res.row = a.row, res.col = a.col;
memset(res.v, 0, sizeof(res.v));
for (int i = 1; i <= a.row; i++)
res.v[i][i] = 1;
while (n != 0)
{
if (n % 2 == 1)
res = mul(res, a);
a = mul(a, a);
n /= 2;
}
return res;
}
long long a[5101];
Matrix f[5101];
int main()
{
int n;
cin >> n;
long long sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum += a[i];
}
Matrix F;
F.col = F.row = 2;
F.v[1][1] = 6;
F.v[1][2] = MOD - 1;
F.v[2][1] = 1;
F.v[2][2] = 0;
Matrix tmp = power(F, sum - 1);
Matrix F_base;
F_base.row = 2; F_base.col = 1;
F_base.v[1][1] = 3; F_base.v[2][1] = 1;
Matrix F_result = mul(tmp, F_base);
int g0 = F_result.v[1][1];
tmp = power(F, sum - 2);
F_result = mul(tmp, F_base);
int g1 = F_result.v[1][1];
f[0].row = f[0].col = 2;
f[0].v[1][1] = f[0].v[2][2] = 1;
f[0].v[1][2] = f[0].v[2][1] = 0;
for (int i = 1; i <= n; i++)
f[i] = add(f[i - 1], mul(f[i - 1], power(F, 2 * a[i])));
Matrix G_base;
G_base.row = 2; G_base.col = 1;
G_base.v[1][1] = g1; G_base.v[2][1] = g0;
Matrix G_result = mul(f[n], G_base);
cout << G_result.v[2][1] << endl;
return 0;
}