ปัญหา
n ลูกอม (Unique/ต่างกันทุกตัว) k ถุง แต่ละถุงต้องมี ≥ 1 ลูก หาจำนวนวิธีแจก (Mod ไม่ได้ระบุ แต่ควร Mod 10^9+7)
ตัวอย่าง
n=3, k=2 → Output: 3
Ways: {(1,2),(3)}, {(1),(2,3)}, {(2),(1,3)}
อัลกอริทึม (Stirling Numbers of the Second Kind × k!)
จำนวนวิธี = S(n, k) × k! โดย S(n,k) = Stirling Number of 2nd Kind (จำนวนวิธีแบ่ง n items เป็น k non-empty unlabeled subsets)
Recurrence: S(n,k) = S(n-1,k-1) + k × S(n-1,k)
DP Table: dp[c][b] = จำนวนวิธีสำหรับ c ลูกอม, b ถุง (1-indexed)
ตัวอย่างโค้ด
def solve(n, k):
dp = [[1] * n for _ in range(n)]
for c in range(2, n):
for b in range(1, min(c, k)):
dp[c][b] = dp[c-1][b-1] + dp[c-1][b] * (b + 1)
return dp[n-1][k-1]
print(solve(3, 2)) # 3หมายเหตุ
โค้ดต้นฉบับไม่มี Modulo ควรเพิ่ม % (10**9+7) สำหรับ n ใหญ่
สูตร Closed Form: Σ(-1)^(k-i) × C(k,i) × i^n / k! (Inclusion-Exclusion)
ความซับซ้อน
- Time: O(n × k)
- Space: O(n²) → ลดได้เป็น O(k) ด้วย Rolling Array
