No.2811 Calculation Within Sequence
タグ : / 解いたユーザー数 121
作問者 :
tfltkpc
/ テスター :
hirayuu_yc
highlighter
Magentor
Yoyoyo8128
zeta7532
Problem Statement
There are integer sequences $T,S$, each consisting of $10^{100}$ terms. The input gives the first $a$ terms of the sequence $T$ and the first $b$ terms of the sequence $S$. All terms other than the given ones are $0$.
Determine whether it is possible to make $T$ and $S$ identical by performing the following operation any number of times, possibly $0$ times.
- Perform one of the following.
- Choose a tuple of distinct integers $p,q,r$ between $1$ and $10^{100}$, inclusive, and replace $T_{r}$ with $T_{p}+T_{q}$.
- Choose a tuple of distinct integers $p,q,r$ between $1$ and $10^{100}$, inclusive, and replace $T_{r}$ with $T_{p}-T_{q}$.
Constraints
- $1 \leq a,b \leq 2 \times 10^{5}$
- $1 \leq T_i,S_i \leq 10^{9}$
- All input values are integers.
Input
The input is given from standard input in the following format.
$a~~~b$
$T_{1} ~~~ T_{2} ~ \ldots ~ T_{a}$
$S_{1} ~~~ S_{2} ~ \ldots ~ S_{b}$
Output
Print Yes if $T$ and $S$ can be made identical by the operations, and No otherwise, followed by a newline at the end.
Sample
Sample 1
Input
3 2 3 7 5 2 8
Output
Yes
For example, the following operations make $T=S$.
1. Replace $T_{2}$ with $T_{1}+T_{3}$. We get $T=(3,8,5,0,0,0...)$.
2. Replace $T_{4}$ with $T_{3}-T_{1}$. We get $T=(3,8,5,2,0,0...)$.
3. Replace $T_{1}$ with $T_{4}+T_{5}$. We get $T=(2,8,5,2,0,0...)$.
4. Replace $T_{3}$ with $T_{5}+T_{6}$. We get $T=(2,8,0,2,0,0...)$.
5. Replace $T_{4}$ with $T_{5}+T_{6}$. We get $T=(2,8,0,0,0,0...)$, which matches $S$.
Therefore, the answer is Yes.
Sample 2
Input
2 3 2 8 3 7 5
Output
No
No matter how the operations are performed, $T$ cannot be made identical to $S$.
Sample 3
Input
5 1 3 3 3 3 3 777
Output
Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。