trang chủ / đề bài / icpc24_nat_f

Alice cuồng nộ

Đề bài

Mô tả

Vừa học được một kỹ năng mới rất mạnh tên là "Cuồng nộ" (Rage Rush), Alice lập tức tới sân tập để làm quen với nó.

Kỹ năng này hoạt động khá đặc biệt. Giả sử khi Alice dùng kỹ năng, đang có k quái vật Marchen còn sống với lượng máu lần lượt là b1,b2,…,bk (một quái vật còn sống nếu nó còn ít nhất 1 máu). Khi đó:

  • Đầu tiên, một Marchen trong k con còn sống được chọn với xác suất tỉ lệ với lượng máu hiện tại của nó. Nói cách khác, xác suất chọn Marchen thứ i là pi=bi∑j=1kbj.
  • Sau đó, một số nguyên trong đoạn [3,5] được chọn, mỗi số có xác suất như nhau, và máu của Marchen được chọn giảm đi đúng số đó. Nếu Marchen có ít máu hơn số bị trừ, phần sát thương dư bị lãng phí (không chuyển sang Marchen nào khác).

Trong sân tập, Alice dựng n hình nộm Marchen với lượng máu ban đầu là a1,a2,…,an. Chúng không đánh trả nên Alice có thể tập bao lâu tùy thích.

Nếu Alice chỉ dùng "Cuồng nộ" để tấn công, hãy tính kỳ vọng số lần Alice dùng kỹ năng cho tới khi tất cả hình nộm đều chết.

Đặt M=998244353. Có thể chứng minh đáp án biểu diễn được dưới dạng phân số tối giản pq với q≢0(modM). Hãy in ra số nguyên x thỏa mãn 0≤x<M và x·q≡p(modM).

Dữ liệu vào

Dòng đầu tiên chứa số bộ test t (1≤t≤104). Tiếp theo là mô tả các bộ test.

  • Dòng đầu tiên của mỗi bộ test chứa số nguyên n (1≤n≤2·105): số hình nộm.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤1018): lượng máu ban đầu của các hình nộm.

Dữ liệu đảm bảo tổng n trên tất cả các bộ test không vượt quá 2·105.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên: kỳ vọng số lần Alice dùng kỹ năng để hạ hết các hình nộm, lấy modulo 998244353.

Ràng buộc

  • 1≤t≤104
  • 1≤n≤2·105, tổng n trên tất cả các bộ test không vượt quá 2·105
  • 1≤ai≤1018

Ví dụ

Input Output Giải thích
3
2
3 5
3
3 4 5
5
1 4 2 9 5
665496238
4
665496243
Bộ test thứ nhất: máu ban đầu là (3,5). Chẳng hạn kịch bản "Marchen 1 về 0, Marchen 2 mất 3 máu, Marchen 2 về 0" có xác suất 38·13=18 và dùng 3 lần kỹ năng. Cộng tất cả 8 kịch bản có thể, kỳ vọng là 83, và 665496238·3≡8(mod998244353).
3
1
1
1
6
2
6 10
1
2
36972018
Một hình nộm 1 máu chết sau đúng 1 lần. Hình nộm 6 máu luôn cần đúng 2 lần. Bộ test thứ ba có kỳ vọng 13327.

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