Asked Jul 27th, 2:32 AM 96 3 1
  • 96 3 1
+3

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

Share
  • 96 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 ANSWERS


Answered Jul 28th, 8:59 AM
0

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

Share
Avatar iamfresher @benkyou
Jul 28th, 1:42 PM

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

1 2 3
1 2 4
1 3 4
2 3 4
0
| Reply
Share
Jul 29th, 2:11 AM

@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

0
| Reply
Share
Avatar iamfresher @benkyou
Jul 29th, 6:52 AM

@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.

0
| Reply
Share
Viblo
Let's register a Viblo Account to get more interesting posts.