2025 年广西预赛

思路

容斥中的交集计数按所选相邻边的图形判断。线性排列每个数字至多有两个邻居，故度数三的分支不可能；三个数字也不能在线性序列中彼此两两相邻。

想法从哪来：“至少一对”相邻很适合补集或容斥，但首先要穷尽哪些数字对不互质。由于数字很少，可以按公因数直接列边，然后把一个排列理解为一条依次经过所有数字的路径。指定禁对相邻，就是要求这条路径包含指定边。 一个事件可压成一个有两个方向的块；多个事件不能无条件相乘，需要看它们连接成什么形状。若连接成一条链，就把整链压成一个块，内部仅有正反两种方向；若互不相交，两块方向独立；若出现三叉或闭三角，就不可能嵌进线性排列。按这个结构算各层交集，最后除以等可能排列总数，并可用穷举小样本作独立核对。

先列出全部不互质的无序数对，再对“指定数对相邻”的事件使用容斥原理。 多个相邻条件若构成一条链，就把整条链视为一个有两种方向的整体；若构成三角形或三叉形则无法同时发生。