solution of 2225G

· · 题解

Update on 2026/04/23: 修改了一处时间复杂度分析的错误。

题意：构造 0,\cdots,n-1 的一个排列 a，使得相邻两项差被集合 S 中的至少一个数整除。保证 \forall x\in S,3x\le n。

首先我们发现，在 g=\gcd S\neq 1 的时候，有 g\mid a_i-a_1，显然不能满足题意。此时问题无解。

在 g=1 时，我们连接 x,(x+S_i) \bmod n。问题转化为求一条哈密顿路径。但是显然不能直接求。

我们观察一下这个问题的性质。首先，钦定一个 x_0\in S，考虑 \bmod x_0 的剩余类。在这个剩余类里面至少有 3 个元素（由 3x_0\le n）保证。我们可以做到不论从哪个点进入这个剩余类，都可以遍历整个剩余类，然后从这个剩余类中最小的一个出去，以便于访问别的剩余类时，不致超出范围。

具体的，假设这个剩余类为 t,t+x_0,\cdots,t+kx_0，哈密顿路径从 t+k_0x_0 进来，我们可以按照 t+k_0x_0,t+x_0,t+2x_0,\cdots,\widehat{t+k_0x_0},\cdots,t+kx_0,t 的顺序进行访问（其中 \widehat{\cdot} 表示去除这一项，好像有人看不懂）。

这样我们就把问题转化为一个由 x_0 个剩余类组成的图上的哈密顿回路问题。直接对于每一个 x_i(\neq x_0)\in S 连边 t\rightarrow(t+x_i)\bmod x_0 即可（就像在做同余最短路那样），然后直接做一个无回溯的 \textrm {dfs} 就可以知道访问剩余类的顺序，进而就可以求出排列了。这里会让人产生疑惑，下面会给出证明。

::::info[简要证明] 首先我们考虑一个更简要的做法。这个做法在理论上的正确性更加明显，但是笔者认为它在实现上比较复杂。

我们发现，这个问题是大致递归的。记录剩余类数量为 b，那么一开始 b=x_0。在考虑 x_i 时，对于之前的 b，如果 \tilde{b}=\gcd(x_i,b)<b，那么我们可以利用连接 s\rightarrow (s+x_i)\bmod b 的手段把 b 个剩余类划分成 \tilde{b} 个循环。然后对这 \tilde b 个循环，又可以视为 \bmod \tilde b 下的剩余系。于是新的 b\leftarrow\tilde b。这个过程可以递归下去，根据 \gcd S=1 的保证，可以做到 b=1。

然后说说为什么之前的做法是对的。我们可以考虑一下按照原方法连成图的结构。它有一些冗余边，因此我们需要说明那些冗余边不会被访问到，由此，在正确性上可以等价于刚才介绍的那个做法。我们可以把它看作一个分层图，约定更前面的 x_i 连的边是更下层，更后面的 x_i 连的边是更上层，那么层数就是使得 \tilde{b}=\gcd(x_i,b)<b 的 x_i 个数。对于每一层的结构，是 \gcd(x_0,x_i) 个孤立的环，其中只有 \tilde b 个是我们想要的。但是，由于 \textrm {dfs} 的性质，那些冗余边不会被访问到。

在 \textrm {dfs} 的过程中，由于边的先后关系顺序，我们会先走最下层的环，然后走完一圈之后，发现这一层的边连接的点被访问过了，于是就会考虑向上一层的边。走上一层的边一步后，又会回到最底层走一个环，然后继续走上一层的边，直到上一层的边走完一个环后，又会走更上一层的边。由此续行直到整张图被访问。在这里，我们看到，对于有效的 x_i 构成的层，要走高层次的边的时候，必须是它对应的那个剩余系的点都通过低层次的边被访问完后，即比它低层次的边连成的子图中，一个连通块已经被访问完了，才能轮到它，连结到其它连通块，由此这一层的冗余边也不会被访问到；对于无效的 x_i 构成的层，比它低层次的边连成的子图中，已经注定了这一层连的所有边都已经在连通块内了，因此永远不会被访问到。 ::::

时间空间复杂度 \mathcal O(nm)，即连边的条数。求求 \gcd 的时间为 O(m\log\log n) ，不是瓶颈。（由于 \gcd 递减，可能可以分析得更紧，但是显然没有必要）。我们还可以采取两个无关紧要的小优化。

::::info[小小优化，不改变时空复杂度] 首先，我们选取最小的那个 x\in S 作为 x_0，这样可以减少剩余类的数量。

其次，我们在求 \gcd 的时候，记录那些 \gcd(x_0,x_1,\cdots,x_k)\neq \gcd(x_0,x_1,\cdots,x_{k-1}) 的 x_k，也就是在“证明”中使得 b 减小的那些 x_k，然后只对它们连边。因为只有这些值才会对最终答案产生影响。 ::::

下面是笔者的 \rm cpp 代码实现。用时和内存消耗都非常非常少。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cassert>
#include<utility>
#include<vector>
#include<cmath>
struct edge{int to,id;edge(int to,int id){this->to=to,this->id=id;}};
std::vector<edge> a[5005];
int t,n,m,vis[5005],p[20],base,now;
std::vector<std::pair<int,int>> s;
std::vector<int> f[5005];
void add(int x,int y,int id){a[x].push_back(edge(y,id));}
void dfs(int v,int id)
{
    vis[v]=1;
    s.push_back(std::make_pair(v,id));
    for (int i=0;i<(int)a[v].size();i++)
    {
        int u=a[v][i].to;
        if (vis[u]) continue;
        dfs(u,a[v][i].id);
        break;
    }
}
void print(int x,int id)
{
    if (!id)
    {
        for (int i=1;i<(int)f[x].size();i++) printf("%d ",f[x][i]);
        printf("%d ",f[x][0]);
    }
    else
    {
        int lst=((x-p[id])%base+base)%base;
        int fst=f[lst][0]+p[id];
        assert(fst<n);
        printf("%d ",fst);
        for (int i=1;i<(int)f[x].size();i++) if (f[x][i]!=fst) printf("%d ",f[x][i]);
        printf("%d ",f[x][0]);
    }
}
int main()
{
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=m;i++) scanf("%d",&p[i]);
        std::sort(p+1,p+m+1);
        int g=p[1];
        for (int i=1;i<=m;i++) g=std::__gcd(g,p[i]);
        if (g!=1) {puts("-1");continue;}
        base=p[1],now=p[1];
        for (int i=0;i<base;i++) f[i].clear(),a[i].clear();
        for (int i=0;i<n;i++) f[i%base].push_back(i);
        for (int i=2;i<=m;i++)
        {
            int t=p[i]%now;
            if (t==0) continue;
            for (int k=0;k<base;k++) add(k,(k+p[i])%base,i);
            now=std::__gcd(now,p[i]);
        }
        s.clear();
        for (int i=0;i<base;i++) vis[i]=0;
        dfs(0,0);
        assert((int)s.size()==base);
        for (int i=0;i<base;i++) print(s[i].first,s[i].second);
        puts("");
    }
    return 0;
}