English · Original
Chinese · Translation
Formal · Original
<center></center>Senor Vorpal Kickass'o invented an innovative method to encrypt integer sequences of length _n_. To encrypt a sequence, one has to choose a secret sequence , that acts as a key.
Vorpal is very selective, so the key should be such a sequence _b__i_, that its cyclic shifts are linearly independent, that is, there is no non-zero set of coefficients _x_0, _x_1, ..., _x__n_ - 1, such that for all _k_ at the same time.
After that for a sequence you should build the following cipher:
In other words, you are to compute the quadratic deviation between each cyclic shift of _b__i_ and the sequence _a__i_. The resulting sequence is the Kickass's cipher. The cipher is in development right now and Vorpal wants to decipher a sequence after it has been encrypted. You are to solve this problem for him. You are given sequences _c__i_ and _b__i_. You are to find all suitable sequences _a__i_.
## Input
The first line contains a single integer _n_ ().
The second line contains _n_ integers _b_0, _b_1, ..., _b__n_ - 1 ().
The third line contains _n_ integers _c_0, _c_1, ..., _c__n_ - 1 ().
It is guaranteed that all cyclic shifts of sequence _b__i_ are linearly independent.
## Output
In the first line print a single integer _k_ — the number of sequences _a__i_, such that after encrypting them with key _b__i_ you get the sequence _c__i_.
After that in each of _k_ next lines print _n_ integers _a_0, _a_1, ..., _a__n_ - 1. Print the sequences in lexicographical order.
Note that _k_ could be equal to 0.
[samples]
Senor Vorpal Kickass'o 发明了一种创新的方法来加密长度为 $n$ 的整数序列。要加密一个序列，需要选择一个作为密钥的保密序列 $b_i$。
Vorpal 非常挑剔，因此密钥应是一个序列 $b_i$，其所有循环移位是线性无关的，即不存在一组非全零的系数 $x_0, x_1, ..., x_{n - 1}$，使得对所有 $k$ 同时成立 $\sum_{i=0}^{n-1} x_i \cdot b_{(i+k) \bmod n} = 0$。
之后，对于序列 $a_i$，你需要构建如下加密结果：
换句话说，你需要计算每个 $b_i$ 的循环移位与序列 $a_i$ 之间的二次偏差。得到的序列即为 Kickass 的加密结果。该加密方法尚在开发中，Vorpal 希望在加密后能够解密序列。你需要帮他解决这个问题。你将获得序列 $c_i$ 和 $b_i$，你需要找出所有符合条件的序列 $a_i$。
第一行包含一个整数 $n$（$1 \le n \le 2000$）。
第二行包含 $n$ 个整数 $b_0, b_1, ..., b_{n - 1}$（$-10^9 \le b_i \le 10^9$）。
第三行包含 $n$ 个整数 $c_0, c_1, ..., c_{n - 1}$（$0 \le c_i \le 10^{18}$）。
保证序列 $b_i$ 的所有循环移位线性无关。
第一行输出一个整数 $k$ —— 满足使用密钥 $b_i$ 加密后得到序列 $c_i$ 的序列 $a_i$ 的数量。
随后在接下来的 $k$ 行中，每行输出 $n$ 个整数 $a_0, a_1, ..., a_{n - 1}$。请按字典序输出这些序列。
注意 $k$ 可能为 0。
## Input
第一行包含一个整数 $n$（$1 \le n \le 2000$）。第二行包含 $n$ 个整数 $b_0, b_1, ..., b_{n - 1}$（$-10^9 \le b_i \le 10^9$）。第三行包含 $n$ 个整数 $c_0, c_1, ..., c_{n - 1}$（$0 \le c_i \le 10^{18}$）。保证序列 $b_i$ 的所有循环移位线性无关。
## Output
第一行输出一个整数 $k$ —— 满足使用密钥 $b_i$ 加密后得到序列 $c_i$ 的序列 $a_i$ 的数量。随后在接下来的 $k$ 行中，每行输出 $n$ 个整数 $a_0, a_1, ..., a_{n - 1}$。请按字典序输出这些序列。注意 $k$ 可能为 0。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $.
Let $ \mathbf{b} = (b_0, b_1, \dots, b_{n-1}) \in \mathbb{R}^n $ be the secret key sequence, such that its $ n $ cyclic shifts are linearly independent over $ \mathbb{R} $.
Let $ \mathbf{c} = (c_0, c_1, \dots, c_{n-1}) \in \mathbb{R}^n $ be the given encrypted sequence.
Let $ \mathbf{a} = (a_0, a_1, \dots, a_{n-1}) \in \mathbb{R}^n $ be the unknown plaintext sequence.
For $ j \in \{0, 1, \dots, n-1\} $, define the $ j $-th cyclic shift of $ \mathbf{b} $ as:
$$
\mathbf{b}^{(j)} = (b_j, b_{j+1}, \dots, b_{n-1}, b_0, \dots, b_{j-1})
$$
The encryption is defined by:
$$
c_j = \sum_{i=0}^{n-1} (a_i - b_{(i+j) \bmod n})^2, \quad \forall j \in \{0, 1, \dots, n-1\}
$$
**Constraints**
1. $ 1 \le n \le 2000 $
2. $ |b_i| \le 10^6 $, $ |c_j| \le 10^{12} $
3. The set $ \{ \mathbf{b}^{(0)}, \mathbf{b}^{(1)}, \dots, \mathbf{b}^{(n-1)} \} $ is linearly independent over $ \mathbb{R} $.
**Objective**
Find all $ \mathbf{a} \in \mathbb{R}^n $ such that:
$$
c_j = \|\mathbf{a} - \mathbf{b}^{(j)}\|_2^2, \quad \forall j \in \{0, 1, \dots, n-1\}
$$
Output the number $ k $ of such sequences $ \mathbf{a} $, followed by all $ \mathbf{a} $ in lexicographical order.
API Response (JSON)
{
"problem": {
"name": "E. Cyclic Cipher",
"description": {
"content": "<center></center>Senor Vorpal Kickass'o invented an innovative method to encrypt integer sequences of length _n_. ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 5000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF901E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "<center></center>Senor Vorpal Kickass'o invented an innovative method to encrypt integer sequences of length _n_. ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Senor Vorpal Kickass'o 发明了一种创新的方法来加密长度为 $n$ 的整数序列。要加密一个序列，需要选择一个作为密钥的保密序列 $b_i$。\n\nVorpal 非常挑剔，因此密钥应是一个序列 $b_i$，其所有循环移位是线性无关的，即不存在一组非全零的系数 $x_0, x_1, ..., x_{n - 1}$，使得对所有 $k$ 同时成立 $\\sum_{i=0}^{n-1} x_...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $. \nLet $ \\mathbf{b} = (b_0, b_1, \\dots, b_{n-1}) \\in \\mathbb{R}^n $ be the secret key sequence, such that its $ n $ cyclic shifts are linearly independent ...",
"is_translate": false,
"language": "Formal"
}
]
}