🎯 Mục tiêu bài học

• Hiểu C(n,k), P(n,k), giai thừa n!.
• Biết cách tính tổ hợp rất lớn mod 1e9+7 bằng tiền xử lý factorial.
• Nhìn được bài toán “phân tích số” dưới góc nhìn đếm phương án.

📘 C(n, k) là gì?

C(n,k) là số cách chọn k phần tử từ n phần tử, không quan tâm thứ tự.

Định nghĩa: C(n,k) = n! / (k! * (n-k)!)

Trong code thi HSG, ta thường tính mod một số nguyên tố lớn (ví dụ 1e9+7) để tránh tràn số.

💻 Tiền xử lý giai thừa (factorial)

Python

MOD = 10**9+7

def modpow(a,e):
    r=1
    while e:
        if e&1: r=r*a%MOD
        a=a*a%MOD
        e//=2
    return r

def modinv(a):
    return modpow(a, MOD-2)

N = 100000
fact = [1]*(N+1)
invfact = [1]*(N+1)

for i in range(1,N+1):
    fact[i] = fact[i-1]*i % MOD

invfact[N] = modinv(fact[N])
for i in range(N-1,-1,-1):
    invfact[i] = invfact[i+1]*(i+1) % MOD

def C(n,k):
    if k<0 or k>n: return 0
    return fact[n]*invfact[k]%MOD*invfact[n-k]%MOD

print(C(10,3))

C++

#include 
using namespace std;
const long long MOD=1000000007;

long long modpow(long long a,long long e){
    long long r=1;
    while(e){
        if(e&1) r=r*a%MOD;
        a=a*a%MOD;
        e>>=1;
    }
    return r;
}
long long modinv(long long a){
    return modpow(a,MOD-2);
}

int main(){
    int N=100000;
    vector fact(N+1),invfact(N+1);
    fact[0]=1;
    for(int i=1;i<=N;i++) fact[i]=fact[i-1]*i%MOD;
    invfact[N]=modinv(fact[N]);
    for(int i=N-1;i>=0;i--)
        invfact[i]=invfact[i+1]*(i+1)%MOD;
    auto C=[&](int n,int k){
        if(k<0||k>n) return 0LL;
        return fact[n]*invfact[k]%MOD*invfact[n-k]%MOD;
    };
    cout<

# Python: số cách tạo tổng S từ các mệnh giá coins
def count_ways(S, coins):
    dp=[0]*(S+1)
    dp[0]=1
    for c in coins:
        for x in range(c,S+1):
            dp[x]+=dp[x-c]
    return dp[S]

print(count_ways(5, [1,2,5]))  # 4 cách

# quy hoạch động 1 chiều như ví dụ count_ways phía trên