問題一覧 > 通常問題

No.2811 Calculation Within Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 117
作問者 : tfltkpc / テスター : hirayuu_yc highlighter Magentor Yoyoyo8128 zeta7532
1 ProblemId : 11078 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-19 21:19:23

問題文

1010010^{100} 項からなる整数列 T,ST,S があります。入力では数列 TT の先頭 aa 項と数列 SS の先頭 bb 項が与えられます。与えられる項以外はすべて 00 です。

以下の操作を 00 回以上好きな回数行うことで、TT と SS を一致させられるか判定してください。

  • 以下のどちらかを行う。
    • 相異なる 11 以上 1010010^{100} 以下の整数の組 p,q,rp,q,r を選び、TrT_{r} を Tp+TqT_{p}+T_{q} で置き換える。
    • 相異なる 11 以上 1010010^{100} 以下の整数の組 p,q,rp,q,r を選び、TrT_{r} を Tp−TqT_{p}-T_{q} で置き換える。

制約

  • 1≤a,b≤2×1051 \leq a,b \leq 2 \times 10^{5}
  • 1≤Ti,Si≤1091 \leq T_i,S_i \leq 10^{9}
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

a   ba~~~b
T1   T2 … TaT_{1} ~~~ T_{2} ~ \ldots ~ T_{a}
S1   S2 … SbS_{1} ~~~ S_{2} ~ \ldots ~ S_{b}

出力

操作によって TT と SS を一致させられるならば Yes 、そうでなければ No と出力し、最後に改行してください。

サンプル

サンプル1
入力
3 2
3 7 5
2 8
出力
Yes

例えば、次のような操作で T=ST=S にすることができます。

1. T2T_{2} を T1+T3T_{1}+T_{3} で置き換える。 T=(3,8,5,0,0,0...)T=(3,8,5,0,0,0...) となる。

2. T4T_{4} を T3−T1T_{3}-T_{1} で置き換える。 T=(3,8,5,2,0,0...)T=(3,8,5,2,0,0...) となる。

3. T1T_{1} を T4+T5T_{4}+T_{5} で置き換える。 T=(2,8,5,2,0,0...)T=(2,8,5,2,0,0...) となる。

4. T3T_{3} を T5+T6T_{5}+T_{6} で置き換える。 T=(2,8,0,2,0,0...)T=(2,8,0,2,0,0...) となる。

5. T4T_{4} を T5+T6T_{5}+T_{6} で置き換える。 T=(2,8,0,0,0,0...)T=(2,8,0,0,0,0...) となり、SS と一致する。

よって、答えはYesです。

サンプル2
入力
2 3
2 8
3 7 5
出力
No

どのように操作を行っても、 TT を SS と一致させることはできません。

サンプル3
入力
5 1
3 3 3 3 3
777
出力
Yes

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。