Yêu cầu thg 7 27, 2021 2:32 SA 130 3 1
  • 130 3 1
+3

Nhờ giúp đỡ về thuật toán - bài toán xác suất thống kê

Chia sẻ
  • 130 3 1

Em đang gặp bài toán như bên dưới.
Nhưng chưa tìm ra được công thức nào để giải cho tối ưu.
Rất mong sự giúp đỡ của mọi người ạ.

Trờ về ngày xưa, trò chơi mà người người nhà nhà đều chơi là bắn bi.Trang là một nhà sưu tập bi cậu ta có sở thích rất đặc biệt là các viên bi cùng màu cậu ta đều để chung vào 1 hộp và đánh số thứ tự mỗi viên bi trong hộp từ 1 ( ví dụ hộp có 5 viên: các viên bi được đánh số 1 , 2 , 3 , 4 , 5 ).

Út sau khi được đến nhà Trang chơi, sau một hồi chơi bắn bi , Út chợt nghĩ ra 1 trò :

“ Đếm số cách để lấy ra mỗi hộp một viên bi sao cho 2 viên bi đôi một khác số thứ tự”

Tuy nhiên, do là con người và Út và Trang thường xảy ra mâu thuẫn, nên Út muốn nhờ bạn lập trình ra 1 chương trình có thể tính được kết quả chính xác.

Giới hạn:

+ n <= 10^5

+ số viên bi trong từng hộp <= 10^5.

Input :

+ Dòng đầu nhập n là số hộp bi của Trang

+ Sau đó là n số thể hiện số bi lần lượt trong hộp.

Ouput:

+ Ghi ra kết quả. Do kết quả có thể lớn lấy mod 10^9 + 7.

Input
3
2 3 4

Output
4

1 CÂU TRẢ LỜI


Đã trả lời thg 7 28, 2021 8:59 SA
0

Bạn có thể liệt kê 4 cách lấy ở ví dụ trên không?

Chia sẻ
Avatar iamfresher @benkyou
thg 7 28, 2021 1:42 CH

@conghdql4 Các cách đó là:

1 2 3
1 2 4
1 3 4
2 3 4
thg 7 29, 2021 2:11 SA

@benkyou Mình không hiểu đề lắm, có thiếu ràng buộc gì đó không nhỉ?
Nếu như chỉ với
“Đếm số cách để lấy ra mỗi hộp một viên bi sao cho 2 viên bi đôi một khác số thứ tự
thì theo Input ở trên mình liệt kê có tận 8 cách.

1 2 3
1 2 4
1 3 2
1 3 4

2 1 3
2 1 4
2 3 1
2 3 4
@benkyou

Avatar iamfresher @benkyou
thg 7 29, 2021 6:52 SA

@quangcuong Đúng rồi bạn. Nếu đề ko cho ví dụ thì mình cũng tính ra ra 8.
C12 * C12 * C12 = 8 (C12 là tổ hợp chập 1 của 2 phần tử).
Tuy nhiên theo cái sample thì mình hiểu là nó sẽ loại bỏ những biến cố trùng nhau.
Ví dụ: 124 với 214 thì chỉ tính là 1 cách thôi.

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí