「SOL」Hamiltonian Cycle (AtCoder) | Lucky_Glass's Blog
0%

「SOL」Hamiltonian Cycle (AtCoder)

原来一般的四度图也没法快速构造哈密顿回路 QwQ


# 题面

给定质数 $P$ 和正整数 $a,b$,构造一个长为 $P$ 的数列 $G=(g_1,g_2,\dots,g_P)$,满足:

  • $g_1=g_P=1$;
  • $(g_1, g_2,\dots,g_{P-1})$ 是 $1\sim P-1$ 的排列;
  • $\forall 1\le i\le P-1$,$g_i$ 和 $g_{i+1}$ 满足下述关系之一:
    • $g_i=ag_{i+1}$;
    • $ag_i=g_{i+1}$;
    • $g_i=bg_{i+1}$;
    • $bg_i=g_{i+1}$。

判断是否有解,若有解,给出任意一组。

数据规模:$P\le10^5,1\le a,b\lt P$。


# 解析

转化为图论问题,若 $i, j$ 满足题面所述的性质,则在 $i, j$ 之间连边。需要找到一条哈密顿回路(经过所有点恰好一次)。显然这个图的每个点度数都是 $4$,虽然没什么用

不额外说明的话,以下的计算均是在模 $P$ 意义下的。

$P$ 是质数,意味着 $a,b$ 都有逆元,进一步意味着「将 $i$ 与 $a\cdot i$ 连边」会得到若干个大小为 $\mathrm{ord}_a$ 的环。

结论

令 $n=\mathrm{ord}_a$,数集 $H=\{a^i\mid i\in \mathbb Z\}$,$m$ 为满足 $b^{m_0}\in H$ 且 $m_0\ge 1$ 的最小 $m_0$。

则问题有解当且仅当 $nm = P - 1$;若 $nm = P - 1$,则 $\forall 1\le x\le P - 1$,存在唯一的 $i \in [0, n), j \in [0, m)$,使得 $x = a ^ i b ^ j$。

根据定义,下述结论是显然成立的: $$ \{a ^ i b ^ j \mid i, j \in \mathbb Z\}=\{a ^ i b ^ j \mid i \in [0, n), j \in [0, m), i,j \in \mathbb Z\} $$ 原问题有解的必要条件是 - $\forall 1\le x\le P - 1$,$\exists i, j \in \mathbb Z, x = a ^ i b ^ j$; 即 $$ \begin{aligned} &\{x\mid 1\le x\le P - 1\}=\{a ^ i b ^ j \mid i, j \in \mathbb Z\}=\{a ^ i b ^ j \mid i \in [0, n), j \in [0, m)\}\\ \Rightarrow&\Big|\{x\mid 1\le x\le P - 1\}\Big| = \Big|\{a ^ i b ^ j \mid i \in [0, n), j \in [0, m)\}\Big|\\ \Rightarrow&P-1=nm \end{aligned} $$ 必要性得证。下证上述结论中的第二条,即可构造出一组解,从而证明充分性。 > 下述 $a$ 的指数上的运算在模 $n$ 意义下,$b$ 的指数上同理在模 $m$ 意义下。 每个数都能表示成 $a^ib^j$ 的形式,存在性显然;只需证明**唯一性**。假设存在一个 $x\in[0,P)$,使得 $x=a^ib^j=a^pb^q$($a,p\in[0,n)$,$b,q\in[0, m)$),则 $$ a^{i-p}\equiv b^{q - j} $$ 若 $j\neq q$,则 $0\lt q-j\lt m$,根据「$m$ 是最小的满足 $b^m\in H$ 的正整数」,$b^{q-j}\neq a^{i-p}$。矛盾,则 $j=q$。 $$ a ^ {i - p} \equiv 1 $$ 若 $i\neq p$,则 $0\lt i - p\lt n$,根据「$n$ 是最小的满足 $a^n=1$ 的正整数」,$a ^ {i - p} \neq 1$。矛盾,则 $i = p$。 所以 $i, j$ 具有唯一性。 于是我们可以用 $a ^ i b ^ j$($i \in [0, n), j \in [0, m)$)唯一表示 $1 \sim P - 1$ 的数,可以按照下述方式构造 $n \times m$ 的表格: - 第 $i$ 行第 $j$ 列放置数 $a ^ {i - 1} b ^ {j - 1}$。 $1 \sim P - 1$ 在表格上恰好出现了一次,且表格上相邻的两个数都有边相连 —— 所以这是一个网格图。 再分析,$P - 1$ 是偶数,$nm = P - 1$,$n, m$ 至少有一个是偶数。行和列至少有一个是偶数的网格图可以直接构造哈密顿回路,可以求解,也证明了结论的充分性。 --- ## # 源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*Lucky_Glass*/
#include <cstdio>
#include <cstring>
#include <algorithm>

#define con(typ) const typ &
const int N = 1e5 + 10;

int mod, va, vb, n, m, nans;
bool vis[N];
int ans[N], powa[N], powb[N];

inline int mul(con(int) a, con(int) b) {return int(1ll * a * b % mod);}

int main() {
scanf("%d%d%d", &mod, &va, &vb);
vis[1] = true;
n = m = 1;
for (int tmp = va; tmp != 1; ++n, tmp = mul(tmp, va))
vis[tmp] = true;
for (int tmp = vb; !vis[tmp]; tmp = mul(tmp, vb), ++m) ;
if ( mod - 1 != 1ll * n * m ) {printf("No\n"); return 0;}
if ( n & 1 ) std::swap(va, vb), std::swap(n, m);
powb[0] = powa[0] = 1;
for (int i = 1; i < n; ++i) powa[i] = mul(powa[i - 1], va);
for (int i = 1; i < m; ++i) powb[i] = mul(powb[i - 1], vb);
ans[++nans] = 1;
for (int i = 0, tmp = 1; i < n; ++i, tmp = mul(tmp, va))
if ( i & 1 )
for (int j = m - 1; j; --j)
ans[++nans] = mul(tmp, powb[j]);
else
for (int j = 1; j < m; ++j)
ans[++nans] = mul(tmp, powb[j]);
for (int i = n - 1; ~i; --i)
ans[++nans] = powa[i];
printf("Yes\n");
for (int i = 1; i <= nans; ++i) printf("%d%c", ans[i], i == nans ? '\n' : ' ');
return 0;
}
--- ## THE END #### Thanks for reading!

满眼繁星占领我内心
撑起腐朽夜空
手点着微芒 想照亮那隐约角落
转瞬即逝 如烟火抱憾落幕
将我隐藏 成为星空崭新的孤岛

——《一封孤岛的信》 By 著小生 / 洛天依

> 一封孤岛的信 - Bilibili