trang chủ / đề bài / icpc26_mn_k

Câu đố tủ khóa II

Đề bài

Mô tả

Bài này là phiên bản ngẫu nhiên của bài Câu đố tủ khóa I, có nội dung như sau.

Một căn phòng có n chiếc tủ khóa, được đánh số từ 1 đến n. Mỗi tủ đang ở trạng thái mở hoặc đóng. Một nhóm gồm n người thừa kế phải giải một câu đố với các tủ này trước khi được nhận tài sản thừa kế.

Những người thừa kế cũng được đánh số từ 1 đến n. Ở mỗi bước, bạn được chọn một người thừa kế để thực hiện một thao tác. Khi người thừa kế thứ i được chọn, người đó đảo trạng thái của mọi tủ có chỉ số là bội của i. Cụ thể hơn, với mọi số nguyên dương j sao cho i×j≤n, trạng thái của tủ thứ (i×j) được đổi từ mở thành đóng hoặc ngược lại. Một người thừa kế có thể được chọn nhiều lần.

Câu đố được giải khi cả n tủ đều đóng.

Hãy tìm một dãy thao tác đóng được tất cả các tủ, hoặc cho biết không tồn tại dãy như vậy.

Bối cảnh và luật chơi giống hệt Câu đố tủ khóa I, chỉ khác là bạn không còn được chọn người thừa kế thực hiện mỗi thao tác. Ở mỗi bước, đúng một người thừa kế được chọn ngẫu nhiên: người thừa kế thứ i được chọn với xác suất ri. Các lựa chọn ở các bước khác nhau là độc lập. Quá trình dừng ngay khi tất cả các tủ đều đóng; nếu ban đầu mọi tủ đã đóng thì không có thao tác nào được thực hiện.

Hãy tính kỳ vọng số thao tác được thực hiện, tính cả thao tác làm cho mọi tủ đóng lại.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên t (1≤t≤100): số bộ dữ liệu.

Mỗi bộ dữ liệu gồm:

  • Dòng đầu tiên chứa hai số nguyên n và S (1≤n≤100, n≤S≤100): số tủ khóa và tổng tất cả các trọng số xác suất.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (0≤ai≤1): trạng thái ban đầu của các tủ, trong đó ai=1 nghĩa là tủ thứ i đang mở và ai=0 nghĩa là tủ đó đang đóng.
  • Dòng thứ ba chứa n số nguyên p1,p2,…,pn (1≤pi≤S, ∑i=1npi=S): ở mỗi bước, người thừa kế thứ i được chọn với xác suất ri=piS.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra kỳ vọng số thao tác theo modulo 998244353 như định nghĩa dưới đây.

Có thể chứng minh rằng kỳ vọng số thao tác luôn là một số hữu tỉ. Hơn nữa, với các ràng buộc của bài, có thể chứng minh rằng nếu biểu diễn số hữu tỉ này dưới dạng phân số tối giản PQ thì Q≢0(mod998244353). Do đó tồn tại duy nhất số nguyên R sao cho R×Q≡P(mod998244353) và 0≤R<998244353. Hãy in ra R.

Ràng buộc

  • 1≤t≤100.
  • 1≤n≤100, n≤S≤100.
  • 0≤ai≤1.
  • 1≤pi≤S, ∑i=1npi=S.

Ví dụ

Input Output Giải thích
8
3 3
0 0 0
1 1 1
3 3
0 0 1
1 1 1
3 3
0 1 0
1 1 1
3 3
0 1 1
1 1 1
3 3
1 0 0
1 1 1
3 3
1 0 1
1 1 1
3 3
1 1 0
1 1 1
3 3
1 1 1
1 1 1
0
7
7
9
10
9
9
7
Ở bộ dữ liệu thứ nhất mọi tủ đã đóng nên quá trình dừng ngay và đáp án là 0. Ở bộ dữ liệu thứ hai chỉ có tủ 3 đang mở. Nếu người thừa kế 3 được chọn đầu tiên (xác suất 13) thì câu đố được giải sau một thao tác; các lựa chọn khác mở thêm tủ và cần thêm thao tác. Xét mọi dãy lựa chọn ngẫu nhiên, kỳ vọng số thao tác là 7.
3
7 67
1 0 0 0 0 1 1
6 7 6 7 6 7 28
11 12
1 1 1 1 1 1 0 1 0 1 0
2 1 1 1 1 1 1 1 1 1 1
15 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
482862219
84701850
32767
Ở bộ dữ liệu thứ nhất, kỳ vọng số thao tác là 48413814955469214029259441760155978400.

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