trang chủ / đề bài / icpc25_mn_g

Mạch điện

Đề bài

Mô tả

Cho một mạch điện gồm một dãy vô hạn công tắc xếp thành một hàng, được đánh số từ trái sang phải bắt đầu từ 0.

Mỗi công tắc ở một trong hai trạng thái: BẬT (đóng) hoặc TẮT (mở). Ban đầu tất cả công tắc đều TẮT.

Quy tắc tương tác giữa các công tắc kề nhau như sau:

  • Nếu một công tắc chuyển từ TẮT sang BẬT, nó không ảnh hưởng đến công tắc nào khác.
  • Nếu một công tắc chuyển từ BẬT sang TẮT, nó làm công tắc ngay bên phải nó đảo trạng thái hiện tại (BẬT thành TẮT hoặc TẮT thành BẬT).

Bạn dự định thực hiện m thao tác. Thao tác thứ i đảo trạng thái của công tắc ai (0≤ai≤n):

  • Nếu công tắc đang BẬT, nó trở thành TẮT (và có thể gây ra phản ứng dây chuyền sang phải theo quy tắc trên).
  • Nếu công tắc đang TẮT, nó trở thành BẬT.

Chi phí của một thao tác là số công tắc bị thay đổi trạng thái (tính cả công tắc được đảo trực tiếp và các công tắc bên phải bị ảnh hưởng do lan truyền).

Tuy nhiên, mỗi thao tác chỉ được thực hiện với một xác suất nhất định:

  • Thao tác thứ i được thực hiện với xác suất pi=uivi.
  • Ngược lại, nó bị bỏ qua với xác suất 1−pi.

Các thao tác được xét lần lượt theo thứ tự từ 1 đến m. Hãy tính kỳ vọng của tổng chi phí của cả m thao tác.

Gọi giá trị kỳ vọng là E=PQ, trong đó P và Q là hai số nguyên nguyên tố cùng nhau. Hãy in ra giá trị (P·Q−1)mod998244353, trong đó Q−1 là nghịch đảo modulo của Q theo modulo 998244353.

Lưu ý: số công tắc là vô hạn, n chỉ là cận trên của các ai trong dữ liệu vào.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n, m (1≤n,m≤2·105): cận trên của các ai và số thao tác.
  • m dòng tiếp theo, mỗi dòng chứa ba số nguyên ai, ui, vi (0≤ai≤n, 0≤ui<998244353, 1≤vi<998244353, ui≤vi): vị trí công tắc và xác suất thực hiện thao tác thứ i dưới dạng phân số pi=uivi.

Dữ liệu ra

In ra một số nguyên duy nhất: giá trị P·Q−1mod998244353, với PQ là kỳ vọng của tổng chi phí các thao tác.

Ràng buộc

  • 1≤n,m≤2·105
  • 0≤ai≤n
  • 0≤ui≤vi, 1≤vi<998244353

Ví dụ

Input Output Giải thích
3 3
0 1 2
1 1 2
2 1 2
499122178 Mỗi thao tác được thực hiện với xác suất 12 và ba thao tác đảo ba công tắc khác nhau đang TẮT, nên mỗi thao tác được thực hiện có chi phí 1. Kỳ vọng là 32, tức 499122178 theo modulo.
100 5
0 100 333
0 333 666
0 666 1234
1 1234 1235
2 1235 1236
610769569 Ba thao tác đầu cùng đảo công tắc 0, nên khi nhiều thao tác được thực hiện sẽ có lan truyền sang các công tắc bên phải.

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