2025 年广东预赛

思路

正常着色指相邻顶点颜色不同。固定首色后，记末色同首色与不同首色的链计数为 $S_r,D_r$，延长一格有 $S_{r+1}=D_r,D_{r+1}=2S_r+D_r$；闭环要求末色不同首色。

想法从哪来：十个数个位互异，等于每个个位类恰取一个候选；每类又有三个候选，所以试把选择编码成三种状态。禁差不是按通常的个位顺序相邻，而是个位每次加三，因此先沿这个步长排列个位类，因三与十互素，它们恰好构成一个十元环。 编码还需处理从个位进到下一十位的进位，不能直接用十位数字作颜色。以模三十的位置建立带偏移的状态，才能使相邻类的禁差恰等价于状态相同，包括环尾接回环头。于是任务成为固定标号环的三色正常着色；可按末点是否与首点同色建立两状态递推推出公式，而不把旋转后的不同选择当成同一个子集。

个位互异且恰选十个数，等价于每个个位数字选一个。按个位数字依次加 $3$ 排成一个 十元环，再把同一个位的三种选择编码成三种颜色。