Soluție HackerRank pentru Emma and sum of products, subdomeniul Algebra, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Emma and sum of products
- Domeniu: Algebra
- Limbaj: C++14
Challenge: Emma and sum of products
Subdomeniu: Algebra (algebra)
Scor cont: 80.0 / 80
Submission status: Accepted
Submission score: 1.0
Submission ID: 464735108
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/emma-and-sum-of-products/problem
Cerință
Emma is really fond of integers and loves playing with them. Her friends were jealous, and to test her, one of them gave her a problem.
Emma is given a list A of N integers and is asked a set of Q queries. Each query is denoted by an integer K, for which you have to return the sum of product of all possible sublists having exactly K elements.
Emma has got stuck in this problem and you being her best friend have decided to help her write a code to solve it. Since the answers can be very large, print the answers modulo 100003.
Input Format
First line has an integer N, denoting the number of integers in list A. Next line contains N space separated integers. The third line contains integer Q, and next Q lines have a single integer K.
Output Format
For each of the queries, print the corresponding answer in a new line.
NOTE Sublist here refers to selecting K elements from a list of N elements. There will be N choose K ways to do that, it doesn't matter if two elements are same.
Constraints
1 ≤ N ≤ 3×10^4
1 ≤ A_i ≤ 10^5
1 ≤ Q ≤ N
1 ≤ K ≤ N
Sample Input #00
3
1 2 3
2
1
2
Sample Output #00
6
11
Sample Input #01
3
1 2 2
1
2
Sample Output #01
8
Explanation
Sample #00:
For K=1 possible sublists are {1},{2},{3} so answer is 1+2+3 = 6.
For K=2 possible sublists are {1,2},{2,3},{3,1} so answer is (1×2) + (2×3) + (3×1) = 2+6+3 = 11.
Sample #01:
For K=2 possible sublists are {1,2},{2,2},{2,1} so answer is (1× 2) + (2×2) + (2× 1) = 2+4+2 = 8.
Cod sursă
//emma-and-sum-of-products.cpp
//Emma and sum of products
//Ad Infinitum - Math Programming Contest August'14
//Author: derekhh
#include<iostream>
#include<cstring>
using namespace std;
const int MOD = 100003;
int a[30001], n;
int f[30001], g[30001];
void foo()
{
f[0] = 1; f[1] = a[1];
for (int i = 2; i <= n;i++)
{
g[0] = 1;
for (int j = 1; j <= i; j++)
g[j] = (f[j] + (long long)f[j - 1] * a[i]) % MOD;
memcpy(f, g, sizeof(g));
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
foo();
int q;
cin >> q;
while (q--)
{
int k;
cin >> k;
cout << f[k] << endl;
}
return 0;
}