問題一覧 > 通常問題

No.1509 Swap!!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 83
作問者 : 遭難者遭難者 / テスター : mine691mine691 oliverx3oliverx3 yuto1115yuto1115
3 ProblemId : 6207 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-13 23:13:30

問題文

あなたは $1$ 以上 $N$ 以下の正整数を並び替えた長さ $N$ の順列 $P=(P_1,P_2,\ldots,P_N)$ に対して以下の $2$ つの操作を好きな順番で 好きな回数 行えます。

・$1\le i \le N-A$ を満たす整数 $i$ を選び、 $P_i$ の値と $P_{i+A}$ の値を入れ替える

・$1\le i \le N-B$ を満たす整数 $i$ を選び、 $P_i$ の値と $P_{i+B}$ の値を入れ替える

あなたの最終的な目標は $P$ を昇順に並び替えることです。 $P$ の初期状態に依らず目標を達成できるか判定してください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • $1\le T\le 5\times10^4$
  • $2\le N\le 10^{18}$
  • $1\le A,B< N$
  • 入力は全て整数

    • 入力

    $T$
$case_1$
$\vdots$
$case_T$
    各テストケースは以下のように与えられる。 
    $N$ $A$ $B$

    出力

    $T$ 行出力せよ。

    $i$ 行目には $i$ 番目のテストケースが目標を達成できるなら YES を、そうでないなら NO を出力せよ。

    サンプル

    サンプル1
    入力
    3
3 1 2
4 2 2
10000000000000000 1122334455667788 9988776655443322
    出力
    YES
NO
NO

    $1$ つ目のテストケースについて考えます。

    例えば初期状態が $3\ 1\ 2$ の場合、

    $3\ 2\ 1$ ($2$ 番目と $3$ 番目を交換)

    $1\ 2\ 3$ ($1$ 番目と $3$ 番目を交換)

    とすることで昇順に並び替えることができます。

    他の長さ $3$ の順列も適切な交換をすることにより昇順に並び替えることができるので、 YES を出力してください。

    $2$ つ目のテストケースは、例えば初期状態が $4\ 3\ 2\ 1$ の場合、どのように並び替えても昇順にすることはできません。

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