原来一般的四度图也没法快速构造哈密顿回路 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
| #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