| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 23 | 4 | 2 | 14.286% |
You are given polynomials $f(x),ドル $g(x),ドル $h(x)$ over field $\mathbb{Z}/2\mathbb{Z}$.
Find the polynomial $f(g(x)) \bmod h(x)$.
The first three lines of input contain polynomials $f,ドル $g$ and $h,ドル one per line. Each polynomial $p$ is descibed as $n$ $p_0$ $p_1$ $p_2$ $\dots$ $p_n$ (1ドル \le n \le 4000,ドル $p_i \in \{0, 1\}$ for all $i,ドル and $p_n = 1$). The polynomial $p(x)$ is then equal to $p_0 + p_1 x + p_2 x^2 + \dots + p_n x^n$.
Print the resulting polynomial in the same format.
If the answer is the null polynomial, print it as "0 0".
5 0 1 0 1 0 1 2 1 1 1 4 0 1 1 0 1
1 1 1
2 1 1 1 3 0 0 1 1 4 1 0 1 0 1
3 1 0 0 1
Let us recall some definitions.
The field $\mathbb{Z}/2\mathbb{Z}$ is a set of two elements 0ドル$ and 1ドル$ where results of addition, subtraction, multiplication and division are remainders modulo 2ドル$ of the corresponding results for ordinary integers.
A polynomial $f(x)$ over this field is an expression of the form $f_n \cdot x^n + f_{n - 1} \cdot x^{n - 1} + \ldots + f_1 x + f_0,ドル where coefficients $f_n,ドル $\ldots,ドル $f_0$ are integers from $\mathbb{Z}/2\mathbb{Z},ドル and the variable $x$ can hold values from $\mathbb{Z}/2\mathbb{Z}$ too. The maximum integer $n$ such that $f_n \ne 0$ is called the degree of the polynomial $p(x)$.
Polynomials $a(x) = \sum \limits _k a_k x^k$ and $b(x) = \sum \limits _k b_k x^k$ are equal if $a_k$ и $b_k$ are equal for all $k$.
Addition and subtraction of polynomials are performed component-wise: $a(x) \pm b(x) = \sum \limits _k (a_k \pm b_k) \cdot x^k$.
The product of polynomials $a(x)$ and $b(x)$ is $c(x) = \sum \limits _k c_k x^k$ where $c_s = \sum \limits _{t = 0} ^{s} (a_t \cdot b_{s - t})$.
Polynomials can be divided by each other. For a non-null polynomial $b(x),ドル we say that $a(x) / b(x) = q(x)$ and $a(x) \bmod b(x) = r(x)$ if $q(x) \cdot b(x) + r(x) = a(x)$ and the degree of $r(x)$ is strictly less than the degree of $b(x)$. It can be shown that $q(x)$ and $r(x)$ are uniquely defined.
Composition $a(b(x))$ is the polynomial $\sum \limits _k a_k (b(x))^k$ where the power of a polynomial is defined via multiplication: $(b(x))^0 = 1,ドル $(b(x))^1 = b(x),ドル $(b(x))^p = b(x) \cdot (b(x))^{p - 1}$ for $p > 1$. To find the coefficients, expand the expression and sum the coefficients for the same powers of $x$.