Return the number of permutations of 1 to n
so that prime numbers are at prime indices (1-indexed.)
(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)
Since the answer may be large, return the answer modulo 10^9 + 7
.
Example 1:
Input: n = 5 Output: 12 Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.
Example 2:
Input: n = 100 Output: 682289015
Constraints:
1 <= n <= 100
A:
1: 忘记了做permutation的时候,和数也可以做permutation的
2: 没有问。 n == 1时, 答案应该是1 还是0. (我默认是0, 结果错了)
3:when res is of int type, its multiplication can suffer overflow.
class Solution { public: int numPrimeArrangements(int n) { vector<int> Prime{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; int nPrimes = 0; for(int i =0;i<Prime.size();i++){ int val = Prime[i]; if(val>n){ break; }else{ nPrimes ++; } } long res = 1; for(int i = 1; i<=nPrimes;i++){ res = (res * i) % 1000000007; } for(int i = 1; i<=n-nPrimes;i++){ res = (res * i) % 1000000007; } return (int)res; } };
No comments:
Post a Comment