构造相邻元素和或差为质数的排列方案

题目背景

这道题要求我们构造一个 $1$ 到 $n$ 的排列，使得任意相邻两个数的和或差的绝对值都是质数。乍一看像是个经典的回溯搜索问题，但如果 $n$ 很大，暴力 DFS 肯定会超时。

核心思路

我们在小规模数据上跑一下，会发现一个有趣的规律：满足条件的排列往往呈现出周期性。经过验证，以长度为 8 的一个特定排列为周期，可以拼接出任意长度的合法序列。

具体来说，如果我们找到了一个长度为 8 的基础循环段，且该段首尾连接处也满足条件，那么对于任意 $n$，我们可以先取前 $n \pmod 8$ 个元素作为前缀，剩下的部分则重复这个基础循环段。关键在于预处理好这几种余数情况下的前缀，以及那个核心的 8 元组。

代码实现

下面给出完整的 C++ 实现。为了效率，我们使用了输入输出加速，并直接硬编码了推导出的最优模式。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 预处理的排列模式
// a[0] 为空占位，a[1]~a[7] 为不同余数的前缀，a[8] 为完整周期
int a[9][9] = {
    {0},
    {1},
    {1, 2},
    {1, 2, 3},
    {1, 2, 3, 4},
    {1, 4, 3, 2, 5},
    {1, 4, 3, 2, 5, 6},
    {1, 4, 3, 2, 5, 6, 7},
    {3, , , , , , , }
};

{
     n;
    cin >> n;
     r = n % ;
    
    
     ( i = ; i < r; ++i) {
        cout << a[r][i] << ;
    }

    
     q = n / ;
     ( i = ; i <= q; ++i) {
         ( j = ; j < ; ++j) {
            
            cout << a[][j] + r + (i - ) *  << ;
        }
    }
    cout << ;
}

{
    ios::();
    cin.();
     t;
    cin >> t;
     (t--) {
        ();
    }
     ;
}