Sắp Xếp Số Nguyên Tố (Prime Arrangements) Trong Python

Tìm số hoán vị của 1..n sao cho các số nguyên tố nằm ở vị trí (index) nguyên tố (1-indexed). Kết quả modulo 10^9 + 7. Ví dụ n=5 → 12 hoán vị. Hợp lệ: [1,2,5,4,3] (số nguyên tố 2,3,5 ở vị trí 2,3,5). Không hợp lệ: [5,2,3,4,1] (5 ở vị trí 1 - không nguyên tố).

Thuật toán

1. Đếm số lượng số nguyên tố ≤ n (gọi là p)
2. Số vị trí nguyên tố cũng là p
3. Số cách sắp xếp = p! × (n-p)! (hoán vị số nguyên tố ở vị trí nguyên tố × hoán vị số hợp số ở vị trí hợp số)
4. Tính modulo 10^9 + 7

Ví dụ (Python)

class Solution(object):
    def getNumPrimes(self, n):
        """Đếm số nguyên tố ≤ n (sieve đơn giản cho n ≤ 100)"""
        if n < 2:
            return 0
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(n**0.5) + 1):
            if is_prime[i]:
                for j in range(i*i, n+1, i):
                    is_prime[j] = False
        return sum(is_prime)
    
    def numPrimeArrangements(self, n):
        MOD = 10**9 + 7
        p = self.getNumPrimes(n)
        
        # Tính p! % MOD
        fact_p = 1
        for i in range(2, p + 1):
            fact_p = (fact_p * i) % MOD
        
        # Tính (n-p)! % MOD
        fact_np = 1
        for i in range(2, n - p + 1):
            fact_np = (fact_np * i) % MOD
        
        return (fact_p * fact_np) % MOD

ob1 = Solution()
print(ob1.numPrimeArrangements(100))  # 682289015

Đầu vào / Đầu ra

Input:  100
Output: 682289015

Tối ưu: Precompute factorial

def numPrimeArrangements(self, n):
    MOD = 10**9 + 7
    # Sieve
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    p = sum(is_prime)
    
    # Factorial
    fact = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = fact[i-1] * i % MOD
    
    return fact[p] * fact[n-p] % MOD