Count Arrangements
Bài tập hôm nay của Nâm liên quan đến số nguyên tố và vị trí của nó. Nâm có một số N. Hãy giúp Nâm đếm số lượng hoán vị của dãy từ 1 đến N mà sao cho các số nguyên tố đều ở vị trí có giá trị là một số nguyên tố (bắt đầu đếm từ 1, vì Nâm là học sinh). Nghe rắc rôi nhỉ, ví dụ như là hoán vị của N = 5 thì [1,2,5,4,3] hợp lệ còn [5,2,3,4,1] thì không vì 5 ở vị trí 1. Kết quả có lẽ sẽ rất lớn, nên trả về kết quả mod 109 + 7.
Ví dụ:
- Với
N = 4thìcountArrangements(N) = 4. Các cách hoán vị đó là:
[1 , 2, 3, 4]; [1, 3, 2, 4]; [4, 2, 3, 1]; [4, 3, 2, 1].
Đầu vào/Đầu ra:
- [Thời gian chạy] 0.1s với C++, 0.6s với Java và C#, 0.8s với Python, Go và JavaScript.
- [Đầu vào] Integer N
1 ≤ N ≤ 104 - [Đầu ra] Integer
Số hoán vị theo đề bài.
Post Comment