Giúp tối ưu code tính tổ hợp chập k của n

#1

Viết chương trình tổ hợp chập k của n theo ct dưới đây:

C(k,\ n)=\frac{n!}{k!×(n-k)!}

Giới hạn đầu vào
1<= k <= n <= 25
Giới hạn thời gian: 1000MS
Giới hạn bộ nhớ: 256 MB

Đây là code của em

#include<bits/stdc++.h>

using namespace std;

unsigned long long gt(int n)
{
    unsigned long long tich = 1;
    for(int i = 1; i<=n; i++)
    {
        tich *= i;
    }
    return tich;
}

unsigned long long tohop(int n, int k)
{
    return gt(n) / (gt(k)*gt(n-k));
}

int main()
{
    int n, k;
    cin >> n >> k;
    if (k>n)
    {
        cout << "Nhap lai: ";
    } else
    {
        cout << tohop(n, k);
    }
    return 0; 
}

Em làm như trên nhưng vẫn bị TLE.
Mong mn có code nào giúp tối ưu hóa thì giúp em với ạ

#2

Từ \large\binom n m bạn tính lên \large\binom {n+1}{m+1}.

3 Likes
#3

Vậy sẽ là return gt(n+1)/(gt(k+1)*gt((n+1)-(k+1))) phải ko ạ

#4

Không phải. Khai triển \large \frac {\binom {n+1}{m+1}}{\binom n m} để tìm công thức truy hồi, rồi tìm điểm bắt đầu nữa là xong.

3 Likes
#5

có giải thích chi tiết ở đây nè :V

3 Likes
#6

Bác tạo 1 hàm lưu lũy thừa sẽ không bị TLE nữa, vì mình không cần tính lại mà đúng không. Có gì lấy giá trị lũy thừa từ mảng lưu vào là được rồi nè.

#7

25! lớn hơn giới hạn của int64 nên không thể tính tổ hợp chập k của n bằng công thức giai thừa được.

2 Likes
#8

vậy tính bằng cách nào vậy ạ, em xem công thức của câu hỏi y chang em vẫn chưa hiểu lắm, mong anh giải thích

#9

Trong đó giống cách mình vừa nói đấy.

2 Likes
#10

ok để mình nghiên cứu thử xem

#11 
#include <bits/stdc++.h>
using namespace std;

long long NcR(int n, int r)
{

	long long p = 1, k = 1;

	// C(n, r) == C(n, n-r),
	// choosing the smaller value
	if (n - r < r)
		r = n - r;

	if (r != 0) {
		while (r) {
			p *= n;
			k *= r;

			// gcd of p, k
			long long m = __gcd(p, k);

			// dividing by gcd, to simplify
			// product division by their gcd
			// saves from the overflow
			p /= m;
			k /= m;

			n--;
			r--;
		}

		// k should be simplified to 1
		// as C(n, r) is a natural number
		// (denominator should be 1 ) .
	}

	else
		p = 1;

	return p;
}

// Driver code
int main()
{
	int n, r;
	scanf("%d",&r);
	scanf("%d",&n);

	printf("%lld",NcR(n, r));

	return 0;
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?