Gương kỳ diệu với truy vấn

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Có $n$ chiếc gương đánh số từ $1$ đến $n$ . Mỗi ngày, một người sẽ hỏi đúng một chiếc gương "Mình có đẹp không?". Gương thứ $i$ sẽ trả lời "đẹp" với xác suất $\frac{p_{i}}{100}$ .

Một số gương được đánh dấu là điểm chốt (checkpoint). Ban đầu chỉ có gương $1$ là điểm chốt, và gương $1$ luôn là điểm chốt.

Người này hỏi các gương theo thứ tự bắt đầu từ gương $1$ . Mỗi ngày, khi hỏi gương $i$ :

Nếu gương $i$ trả lời "đẹp": nếu $i = n$ thì kết thúc; ngược lại ngày hôm sau sẽ hỏi gương $i + 1$ .
Nếu gương $i$ trả lời "không": ngày hôm sau sẽ bắt đầu lại từ điểm chốt có chỉ số lớn nhất không vượt quá $i$ .

Có $q$ truy vấn, mỗi truy vấn cho một số nguyên $u$ : nếu gương $u$ hiện chưa phải điểm chốt thì đánh dấu nó là điểm chốt; ngược lại bỏ đánh dấu.

Sau mỗi truy vấn, hãy in ra số ngày kỳ vọng cho đến khi quá trình kết thúc.

Vì kết quả là một số hữu tỉ, hãy in ra theo modulo $M = 998244353$ . Nếu kết quả viết được dưới dạng phân số tối giản $\frac{a}{b}$ với $b ≢ 0 (\mod M)$ , hãy in ra số nguyên $x$ thỏa $0 \leq x < M$ và $x \cdot b \equiv a (\mod M)$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $q$ .
Dòng thứ hai chứa $n$ số nguyên $p_{1}, p_{2}, \dots, p_{n}$ .
Mỗi dòng trong $q$ dòng tiếp theo chứa một số nguyên $u$ — truy vấn tương ứng.

Dữ liệu ra

Gồm $q$ dòng, mỗi dòng là đáp án của một truy vấn theo modulo $998244353$ .

Ràng buộc

$2 \leq n, q \leq 2 \cdot 10^{5}$ .
$1 \leq p_{i} \leq 100$ .
$2 \leq u \leq n$ (gương $1$ luôn là điểm chốt, không thể bị bỏ đánh dấu).

Ví dụ

Input	Output	Giải thích
2 2 50 50 2 2	4 6	Sau truy vấn 1: điểm chốt là ${1, 2}$ . Mỗi gương có xác suất "đẹp" là $1 / 2$ , kỳ vọng để vượt qua một gương là $2$ ngày, tổng là $4$ . Sau truy vấn 2: điểm chốt chỉ còn ${1}$ , kỳ vọng để vượt qua $2$ gương (khởi động lại từ gương $1$ khi thất bại) là $6$ .
5 5 10 20 30 40 50 2 3 4 5 3	117 665496274 332748143 831870317 499122211	Mỗi truy vấn lần lượt thay đổi tập điểm chốt; các đáp án sau đó được lấy theo modulo $998244353$ .

Bình luận

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