HackerRank Algebra – Emma and sum of products

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

Cerinta

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 \le N \le 3\times10^4$  
$1 \le A_i \le 10^5$  
$1 \le Q \le N$  
$1 \le K \le 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\times2) + (2\times3) + (3\times1) = 2+6+3 = 11$.

Sample #01:  
For $K=2$ possible sublists are $\{1,2\},\{2,2\},\{2,1\}$ so answer is $(1\times 2) + (2\times2) + (2\times 1) = 2+4+2 = 8$.

Cod sursa

//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;
}