前两题我的思路和题解基本相同，第四题我的想法也是和题解基本一致的，甚至思考过程都差不多（从斐波那契进行优化），可惜最后时间不够差一点没写完。（另外两题我压根没看懂orz）

# 以下为Div. 1中不同于Div. 2的两题

# E. Cyclic Cipher

*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:

*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.

### Examples

##### input

1 2 3 |
1 1 0 |

##### output

1 2 |
1 1 |

##### input

1 2 3 |
1 100 81 |

##### output

1 2 3 |
2 91 109 |

##### input

1 2 3 |
3 1 1 3 165 185 197 |

##### output

1 2 3 |
2 -6 -9 -1 8 5 13 |

# 以下为官方题解（前五题为Div. 2，后五题为Div. 1）

### 902A – Visiting a Friend

Note that if we can get to some point x, then we can get to all points <= x. So we can support the rightmost point where we can get to. Then if this point can use the teleport (if this point is to the right of the teleport), we’ll try to move it (If the limit of the teleport is to the right of the current point, then move it there). Then in the end we need to check that the rightmost point where we can get is equal to M.

### 902B – Coloring a Tree

Consider the process from the end, we will “delete” any subtree from the tree, whose color of the ancestor of the highest vertex differs from the color of the highest vertex and the colors of all vertices in the subtree are the same. Thus, we can show that the answer is the number of edges whose ends have different colors + 1.

### 901A – Хешируем деревья

There are many ways to solve the problem. First of all you should build any single tree. To do this, you first build the longest path from the root and then attach remained vertices on proper heights. Thus each vertex is either on the longest path or has parent on this path. To build the second tree you should use different vertices from previous levels during construction to make it different from first tree. This is always possible if there are two consecutive *a*_{i} > 1. Otherwise the tree is determined uniquely by *a*_{i} sequence.

### 901B – НОД многочленов

As for integers it is well known that worst case are consequent Fibonacci’s numbers *F*_{n + 1} = *F*_{n} + *F*_{n - 1}. Solutions to this problem are based on the same idea. There were two main intended solutions. First of all you should note that sequence

*p*

_{0}= 1,

*p*

_{1}=

*x*,

*p*

_{n + 1}=

*x*·

*p*

_{n}±

*p*

_{n - 1}

*p*

_{n}and

*p*

_{n - 1}. It can be directly checked for given constraints that you can always choose + or - to satisfy coefficients constraints.

The other solution is the same sequence but you use + instead of ± and take coefficients modulo 2. That’s true because if remainders sequence has *k* steps while you consider numbers by some modulo it will have at least *k* steps in rational numbers. So the second intended solution is

*p*

_{0}= 1,

*p*

_{1}=

*x*,

### 901C – Bipartite Segments

If two cycles of odd length intersect, then they can be bypassed so as to obtain an edge-simple cycle of even length.

It follows that the given graph is a vertex cactus, with cycles of odd length, then the vertex segment is good – if there is no loop, that the vertex with the minimum number from this cycle is present on this segment and the vertex with the maximum number from this cycle is present on this segment. Then we can select all the cycles, and now we work with the segments.

Let us find for each vertex a maximal right boundary such that the interval [*i*..*mx*_{i}] is a bipartite graph.

Then *mx*_{i} is equal to the minimal right boundary of the segment, which was opened later *i*.

This can be considered a minimum on the suffix, initially setting for all cycles *mx*[minimum on the cycle] = maximum on the cycle

To answer the query, we need to take the sum over *mx*_{i} - *i* + 1 for those who have *mx*_{i} ≥ *r* and the sum over *r* - *i* + 1 for those who have *mx*_{i} ≥ *r*

then we note that *mx*_{i} increases and we simply need to find the first moment when *mx*_{i} becomes ≥ *r* (we can do it with binary search)

And take two prefix sums – sum of (*mx*_{i} - *i* + 1) and sum of *i*.

### 901D – Weighting a Tree

Let’s solve two cases.

First case is when graph is the bipartite graph

Then the sum of weights of the left part should be equal to the sum of weights of the right part (because each edge will bring an equal contribution to the sums of both part).

We will leave any spanning tree of this graph, then for it the solution is unique (take the edges entering the leafs, their weights are uniquely determined, subtract weights from weights of the second ends of this edges, delete the leafs, recursively) this solution can be found with dfs, then in the end, the root will has weight 0 (because sum of weights of the left part equal to the sum of weights of the right part) Thus, the answer exists when the sum of the weights of the left part is equal to the sum of the weights of the right part.

Second case when graph has the odd cycle.

We find an odd cycle, root the tree for any of its vertices, solve the tree. Then, we add to the weights of the edges of the cycle adjacent to the root minus its weight divided by 2 (it is even, because it is the sum of the weights of all vertices (with different signs) equal to the sum of the degrees of vertices by modulo 2). , and for all others we alternate the signs with which we add this value, then for all vertices except the root the sum does not change, but for the root we get the required value.

Example code: https://pastebin.com/b2bGp4Bh

### 901E – Cyclic Cipher

(*a* - *b*)^{2} = *a*^{2} + *b*^{2} - 2*ab*, hence, . Let *a*‘_{i} = *a*_{i} - *a*_{i - 1}, . Then . This corresponds to cyclic convolution of polynomials and . These polynomials uniquely determined by values in roots of unity of degree *n*. Thus we can divide values of *C* by values of *B* in this points and return to polynomials from values in roots of unity. To do this one should compute discrete Fourier Transform in arbitrary length polynomial which can be done by Bluestein’s algorithm. Note that you can’t use complex fft here because real values can be very close to zero leading to great precision issues. Thus you should find some mod having root of unity of degree 2*n*and compute discrete transform over it. Thus we will find *d*_{k} = *a*_{k} - *a*_{0} for each *k*, which will allow us to recover *a*_{0}, because .

It can be proven that values of polynomial in roots of unity are eigenvalues of matrix of linear system thus cyclic shifts are linearly independent iff there is such mod which has root of unity of degree *n* and values of polynomial in all such roots doesn’t equal zero. If it’s true for polynomial in field of real numbers there will be only finite number of mods in which this may not be true (it only true if of polynomial and *x*^{n} - 1 isn’t equal 1 in such mod).