1175. Prime Arrangements

题目信息

题号:

1175

难度:

Easy

主题:

数学、质数、排列计数

原题:

LeetCode 1175

重点:

排列使用 1 到 n 各一次;质数必须恰好放在质数编号位置,结果对 10^9+7 取模

题目重述

把整数 1 到 n 排列到编号为 1 到 n 的位置中,每个整数恰好使用一次。

要求一个数是质数当且仅当它所在的位置编号也是质数。请返回满足条件的不同排列数量,并对 10^9 + 7 取模。数字 1 不是质数。

1 <= n <= 100。

自建示例

质数位置和非质数位置各有三个:

输入:n = 6
输出:36
解释:质数 2、3、5 可在三个质数位置任意排列,共 3! 种;1、4、6 在其余位置也有 3! 种,总数为 3! * 3! = 36。

只有一个数字:

输入:n = 1
输出:1
解释:数字 1 与位置 1 都不是质数,唯一排列满足条件。