Tuco & Polynomials

0

0 votes
Medium-Hard
Problem

Tuco Salamanca is one dangerous guy as we all know. One day Heisenberg and Jesse were trapped inside his house. They were unable to get out of his house.

enter image description here

The DEA gets to know about a hint of their location. To get the location, they need to solve the given problem.

Given a polynomial p(x) of degree n. Let's define P(x) = p(x) power N. That means p(x) multiplied N times. Let's say C(i) denote the coefficient of xi in P(x).

Now you need to answer Q queries of the following form:-

Given an integer d which is power of 2. Compute the sum of coefficients C(jxd) of P for all integer j such that (0 < j x d ≤ degreeOfP). Since the answer can be huge, you need to print only the answer modulo 114689. Please note that it is a prime number.

Can you help them out?

INPUT

  • First line contains three space separated integers n, N and Q denoting degree of the polynomial p, power to be raised to get P from p and number of queries respectively.
  • Next line contains n+1 space separated integers, ith of which, let's call it c(i), denote the coefficient of x^i in p(x) for all 0 ≤ i ≤ n.
  • Next Q lines contains one integer each line, d. You need to compute the described sum for this d.

OUTPUT

  • Output should contain exactly Q lines. Each line containing the answer to the corresponding query.

CONSTRAINTS

  • 1 ≤ n ≤ 100000
  • 1 ≤ N ≤ 1012
  • 1 ≤ Q ≤ 15
  • 0 < d ≤ 16384
  • 0 ≤ c(i) < 114689
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Given polynomial p(x) = 0 + x + 2x2 and exponent N = 3

Hence, P(x) = p(x)3 = 0 + 0x + 0x2 + 1x3 + 6x4 + 12x5 + 8x6

For first query we need to sum coefficients of x 1, x2 ... x6. That is 0 + 0 + 1 + 6 + 12 + 8 which is equal to 27.

For second query we need to sum coefficients of x2, x4 and x6. That is 0 + 6 + 8 which is equal to 14.

For third query we need coefficients of x4 only. That is 6.

Editor Image

?