2.10　质数排列

题目描述（第1175题）

请你帮忙给从1到n的数设计排列方案，使所有的质数都被放在质数索引（索引值从1开始）上；你需要返回可能的方案总数。

让我们一起来回顾一下质数：质数一定是大于1的，并且不能用两个小于它的正整数的乘积来表示。

由于答案可能会很大，所以请你返回答案模mod 109+7 之后的结果即可。

示例1

输入：n=5

输出：12

解释：举个例子，[1,2,5,4,3]是一个有效的排列，但[5,2,3,4,1]不是，因为在第2种情况下质数5被错误地放在索引值为1的位置上了。

示例2

输入：n=100

输出：682289015

提示

1≤n≤100。

思路

这道题其实就是输出全排列的个数，并且这个全排列有要求，即所有的质数都应该被放在质数索引（索引值从1开始）上。由于不需要返回每一个排列，因此这道题相对比较简单。

符合直觉的思路是算出所有的排列然后判断是否满足“所有的质数都在质数索引上”，如果是，则计数器+1。最后返回计数器的值即可。由排列组合原理可知，这种时间复杂度是阶乘，很明显会超时，我们需要换一种思路。

先观察一下题目给的例子。

上图中灰色表示质数，白色表示非质数。两者具有非相关性，并且彼此不可以在对方的位置出现。也就是说，可以将原问题分解为两个独立的子问题，最后的结果就是两个独立子问题的排列数的乘积，而两个子问题分别是“质数的排列”和“非质数的排列”。假设n以内（包括n）一共有m个质数，那么由排列组合原理可知其结果分别是m!和(n-m)!，因此最终结果即为m!×(n-m)!。

由于题目中n的范围是1≤n≤100，我们将所有的质数写出来，类似技巧也会用在26个字母等有限集合中，这个技巧会在第20章进行详细讲解。

代码

复杂度分析

●　时间复杂度：算法的瓶颈在于计算factorial的部分，因此总的时间复杂度为O(n)。

●　空间复杂度：这里使用了递归来求解factorial，因此总的空间复杂度为O(n)，不过你完全可以使用迭代的方法求解。