BinaryPolynomialDivOne | Topcoder Archive

Problem Statement

Warning: This problem statement contains superscripts and/or subscripts. It may not display properly outside of the applet.

In this problem we will consider binary polynomials. A binary polynomial P of degree n, where n is a nonnegative integer, is given by a sequence of coefficients: n+1 zeroes and ones a[0], a[1], ..., a[n], where a[n] = 1. They represent the following:

P(x) = a[0] * x⁰ + a[1] * x¹ + ... + a[n] * xⁿ

Binary polynomials can be evaluated in points 0, 1 and multiplied by each other just like ordinary polynomials, with one exception: all calculations take place modulo 2. For example, we assume that (x + x³) * (1 + x²) = x + 2 * x³ + x⁵ = x + x⁵. Since we can multiply binary polynomials, we can also raise them to positive integer powers; for example, if P = 1 * x⁰ + 0 * x¹ + 1 * x² and m = 3, then P^m = 1 * x⁰ + 0 * x¹ + 1 * x² + 0 * x³ + 1 * x⁴ + 0 * x⁵ + 1 * x⁶.

You are given integers m, k and a binary polynomial P as the array a of its coefficients. Return the coefficient that stands by x^k in the binary polynomial P^m.

Definition

Class:: BinaryPolynomialDivOne
Method:: findCoefficient
Parameters:: int[], long, long
Returns:: int
Method signature:: int findCoefficient(int[] a, long m, long k)
(be sure your method is public)

Constraints

The degree of P will be between 0 and 49, inclusive.
a will contain exactly n+1 elements, where n is the degree of P.
Each element of a will be either 0 (zero) or 1 (one).
a[n] will be equal to 1 (one).
m will be between 1 and 1016, inclusive.
k will be between 0 and n * m, inclusive.

Examples

```
{1, 0, 1}
```
```
3
```
```
4
```
```
Returns: 1
```
This corresponds to the example from the problem statement. Pm equals 1 + x2 + x4 + x6. The coefficient by x4 is hence 1.
```
{1, 0, 1}
```
```
3
```
```
5
```
```
Returns: 0
```
This is the same polynomial as in the previous example.
```
{0, 0, 1, 1, 0, 1}
```
```
7
```
```
15
```
```
Returns: 1
```
```
{1}
```
```
1
```
```
0
```
```
Returns: 1
```

{1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0,
 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1}

2229508454872453

96130299655104846

Returns: 1

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.