#P13696. [ARC118D] Hamiltonian Cycle

    ID: 12898 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-群排列构造奇偶性分析模逆元费马小定理快速幂

[ARC118D] Hamiltonian Cycle

题目描述

给定素数 PP 以及正整数 a, ba,\ b。请判断是否存在一个长度为 PP 的整数序列 A=(A1,A2,…,AP)A = (A_1, A_2, \ldots, A_P),满足以下所有条件。如果存在,请输出其中一个满足条件的序列。

  • 1≤Ai≤P−11 \leq A_i \leq P-1
  • A1=AP=1A_1 = A_P = 1
  • (A1,A2,…,AP−1)(A_1, A_2, \ldots, A_{P-1}) 是 (1,2,…,P−1)(1, 2, \ldots, P-1) 的一个排列
  • 对于任意 2≤i≤P2 \leq i \leq P,下列四个条件至少有一个成立:
    • Ai≡aAi−1(modP)A_i \equiv aA_{i-1} \pmod{P}
    • Ai−1≡aAi(modP)A_{i-1} \equiv aA_i \pmod{P}
    • Ai≡bAi−1(modP)A_i \equiv bA_{i-1} \pmod{P}
    • Ai−1≡bAi(modP)A_{i-1} \equiv bA_i \pmod{P}

输入格式

输入从标准输入读入,格式如下:

PP aa bb

输出格式

如果存在满足条件的整数序列 AA,输出 Yes,否则输出 No。如果输出 Yes,第二行输出该整数序列 AA 的各个元素,空格分隔。

A1 A2 … APA_1\ A_2\ \ldots\ A_P

如果存在多个满足条件的序列,输出任意一个均可。

输入输出样例 #1

输入 #1

13 4 5

输出 #1

Yes
1 5 11 3 12 9 7 4 6 8 2 10 1

输入输出样例 #2

输入 #2

13 1 2

输出 #2

Yes
1 2 4 8 3 6 12 11 9 5 10 7 1

输入输出样例 #3

输入 #3

13 9 3

输出 #3

No

输入输出样例 #4

输入 #4

13 1 1

输出 #4

No

说明/提示

数据范围

  • 2≤P≤1052 \leq P \leq 10^5
  • PP 是素数
  • 1≤a,b≤P−11 \leq a, b \leq P-1

样例解释 1

以 P=13P=13 为例,满足以下条件:

  • A2≡5A1A_2 \equiv 5A_1
  • A2≡4A3A_2 \equiv 4A_3
  • ⋮\vdots
  • A13≡4A12A_{13} \equiv 4A_{12}

可以确认该整数序列满足所有条件。