题目描述

塔子哥拿到了 $n$ 个数 $a_i$ ，他想知道，使用这些数构造一个长度为 $n$ 的数组，且满足相邻两个数的和均为素数，共有多少种不同的数组构造方案。

题解

抽象一下题意，给定 $n$ 个数 $a_i$，随机排列后求有多少种情况满足相邻的两个数的和都是素数。

原题给的 $n$ 最大为12， 这样直接暴力是很大概率超时的，需要用状压DP来解决，比较繁琐。

根据塔子哥的群友描述，本题直接暴力在机试的时候也是能够全过的，因此本题将数据范围缩小至 $n \le 8$