trang chủ / đề bài / icpc26_nat_c

Kẹo nhiều màu

Đề bài

Mô tả

Bạn có một hũ kẹo ma thuật rất lớn gồm n màu khác nhau. Các màu được đánh số từ 1 đến n, và ban đầu màu thứ i có ci viên kẹo.

Chừng nào các viên kẹo trong hũ chưa cùng một màu, bạn thực hiện thao tác sau:

  • Chọn hai viên kẹo khác màu, ngẫu nhiên đều trong tất cả các cặp kẹo như vậy.
  • Sau đó, chọn một trong hai viên kẹo này, ngẫu nhiên đều, và đổi màu của nó thành màu của viên kẹo còn lại.

Hãy tìm kỳ vọng số thao tác được thực hiện cho đến khi tất cả các viên kẹo trong hũ có cùng một màu.

Dữ liệu vào

Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu τ (1≤τ≤300). Tiếp theo là mô tả các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa số nguyên n (1≤n≤300), số màu.

Dòng thứ hai chứa n số nguyên c1,c2,…,cn (1≤ci≤109), số viên kẹo của mỗi màu.

Dữ liệu đảm bảo tổng n qua tất cả các bộ dữ liệu không vượt quá 300.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra đáp án như sau:

  • Nếu kỳ vọng số thao tác là vô hạn, in ra −1.
  • Ngược lại, đặt M=109+7. Có thể chứng minh rằng khi đó kỳ vọng số thao tác biểu diễn được dưới dạng phân số tối giản pq, trong đó p, q là các số nguyên và q≢0(modM). In ra số nguyên bằng p·q−1modM. Nói cách khác, in ra số nguyên x sao cho 0≤x<M và x·q≡p(modM).

Ràng buộc

  • 1≤τ≤300.
  • 1≤n≤300; 1≤ci≤109.
  • Tổng n qua tất cả các bộ dữ liệu không vượt quá 300.

Ví dụ

Input Output Giải thích
3
2
1 1
2
2 1
1
5
1
2
0
Bộ thứ nhất: có hai viên kẹo khác màu, sau một thao tác cả hai cùng màu, đáp án là 1. Bộ thứ hai: có hai viên màu 1 và một viên màu 2. Ở thao tác đầu tiên, cặp được chọn gồm viên màu 2 và một viên màu 1. Với xác suất 12, viên màu 2 đổi thành màu 1 và mọi viên kẹo cùng màu. Với xác suất 12, viên màu 1 đổi thành màu 2: khi đó có một viên màu 1 và hai viên màu 2, giống tình huống ban đầu với hai màu đổi chỗ. Vậy số thao tác tuân theo phân phối hình học với xác suất thành công 12, kỳ vọng là 2. Bộ thứ ba: mọi viên kẹo đã cùng màu nên không có thao tác nào.
2
3
1 2 3
2
1000000000 1000000000
11
49
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: kỳ vọng số thao tác là 11. Bộ thứ hai: kỳ vọng là 1018, phần dư khi chia cho 109+7 là 49.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0