Đây là bài toán tổ hợp lặp
Có K tiền, bỏ K tiền vào N hộp, có bao nhiêu cách
= (K+N-1) C (N-1)
bài toán có kết quả lớn và chỉ lấy 9 chữ số cuối cùng :) ta không thể sử dụng field (modular calculation) .
Bản chất của tổ hợp là
n! / (n-k)! / k!
ta sẽ dùng phương pháp rút gọn cổ điển :) . Sau đó sẽ ra con số lưu trữ được trong long.
ta có kết quả là : (n-k-1) ! / (n-1)! / k!
ta chọn (n-1)! rút gọn
sẽ tương đương : [ n*(n+1)*(n+2)*...*(n-k-1) ] / [2*3*...k]
ta luôn chắc chắn phép chia trên là hết; vậy nên ta thực hiện rút gọn theo gcd(ts[i], ms[j]), lúc này ms=empty;
thực hiện tính tích các phần tử trong ts và % cho 1e9;
int gcd(int a, int b){
if(a==0) return b;
return gcd(b%a, a);
}
int solve(int n, int k) {
vector<int> ts, ms;
int left = (n+k-1);
int right = n-1;
int l_r = k;
for(int i=2;i<=l_r;++i){
ms.push_back(i);
}
for(int i=right+1; i <= left;++i){
ts.push_back(i);
}
long ret = 1;
for(int i=0;i<ts.size();++i){
for(int j=0;j<ms.size();++j){
int cm = gcd(ts[i],ms[j]);
if(cm > 1){
ts[i]/= cm;
ms[j]/= cm;
if(ts[i] == 1) break;
}
}
ret *= ts[i];
ret %= 1000000000;
}
return ret;
}
Đây là bài toán tổ hợp lặp Có K tiền, bỏ K tiền vào N hộp, có bao nhiêu cách
= (K+N-1) C (N-1)
bài toán có kết quả lớn và chỉ lấy 9 chữ số cuối cùng :) ta không thể sử dụng field (modular calculation) .
Bản chất của tổ hợp là n! / (n-k)! / k!
ta sẽ dùng phương pháp rút gọn cổ điển :) . Sau đó sẽ ra con số lưu trữ được trong long.
ta có kết quả là : (n-k-1) ! / (n-1)! / k!
ta chọn (n-1)! rút gọn sẽ tương đương :
[ n*(n+1)*(n+2)*...*(n-k-1) ] / [2*3*...k]ta luôn chắc chắn phép chia trên là hết; vậy nên ta thực hiện rút gọn theo gcd(ts[i], ms[j]), lúc này ms=empty; thực hiện tính tích các phần tử trong ts và % cho 1e9;