第2题-塔子哥的相邻素数组 - Problem Detail

会员或题库专享

请先，开通会员或购买题库腾讯音乐机考编程题库，可解锁完整内容。

购买腾讯音乐机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（腾讯音乐机考编程题库），可解锁完整内容。

购买题库开通会员

题解

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

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

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

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