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

ID: 861

Difficulty: 5

所属公司 : 腾讯音乐

时间 :2024年3月28日

题目描述

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

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

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

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