Tính số tổ hợp nCr với n và r lớn trong c++

#1

Cho hai số n và r, hãy tìm C(n, r)% P. Trong đó, P = 10^9+7.

Input:

  • Dòng đầu tiên đưa vào số lượng test T.
  • Những dòng kế tiếp đưa vào các bộ test. Mỗi test là bộ đôi n, r. Các số được viết cách nhau một vài khoảng trống.
  • T, n, r thỏa mãn ràng buộc : 1≤T≤100; 0≤n≤10^3; 1≤ r ≤800.

m. cho em hỏi có cách nào chuyển phép toàn vày về kiểu chuỗi không ạ? với n, r lớn như vậy thì em làm bình thường toàn bị trà số

#2

C(n, r) là gì? Là chỉnh hợp? Hay là một hàm tính toán gì đó do ông tên C định nghĩa
Nếu là chỉnh hợp thì bạn phải nói rõ hoặc viết format theo công thức toán học

Update: mùnh để ý thì thấy tiêu đề đã có nhắc đến tổ hợp
Vậy bạn có thể nói vì sao bạn muốn biến phép tính thành chuỗi không

2 Likes
#3

Biểu thức có modulo mà, đâu cần chuỗi :smiley:

Đầu tiên bạn phải dùng biến 8 byte (nên dùng uint64_t) thì mới không tràn. Kế tiếp là đi tìm công thức truy hồi. Sau cùng là cài đặt “phép chia” modulo (hay nói cách khác là tìm nghịch đảo)

2 Likes
#4

mình có đề cập lí do ở cuối đấy. Nếu xử lí bình thường thì bị tràn số, ví dụ 1000C130 thì đáp số là 2,4296…*10^57

#5

nhưng đáp án là một số nhỏ hơn 10^9
nhân tới đâu thì chia cho số đó

(a * b * c) % P = ((((a % P) * b) % P) * c) % P

thay vì tính như bên về trái để tràn số, thì hãy tính như bên vế phải

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