1175. Prime Arrangements¶
题目信息¶
- 题号:
1175
- 难度:
Easy
- 主题:
数学、质数、排列计数
- 原题:
- 重点:
排列使用
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 都不是质数,唯一排列满足条件。