Tháp phát sóng

Điểm: 5,00 (OI)

Giới hạn thời gian: 2.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 + 2$ thị trấn nằm trên trục số, được đánh số từ $0$ đến $n + 1$ . Thị trấn thứ $i$ nằm tại điểm $i$ .

Tại mỗi thị trấn $1, 2, \dots, n$ , một tháp phát sóng vô tuyến được xây dựng với xác suất $\frac{1}{2}$ (các sự kiện này độc lập). Sau đó, bạn muốn đặt công suất tín hiệu cho mỗi tháp là một số nguyên từ $1$ đến $n$ (các công suất không nhất thiết phải bằng nhau và cũng không nhất thiết phải khác nhau). Tín hiệu từ tháp đặt tại thị trấn $i$ với công suất $p$ phủ tới mọi thị trấn $c$ thỏa mãn $| c - i | < p$ .

Sau khi xây xong các tháp, bạn muốn chọn công suất tín hiệu sao cho:

Thị trấn $0$ và thị trấn $n + 1$ không nhận được tín hiệu từ bất kỳ tháp nào;
Mỗi thị trấn $1, 2, \dots, n$ nhận được tín hiệu từ đúng một tháp.

Hãy tính xác suất rằng sau khi xây các tháp, tồn tại cách đặt công suất tín hiệu thỏa mãn mọi ràng buộc trên.

Có thể chứng minh được xác suất cần tìm biểu diễn được dưới dạng phân số tối giản $\frac{x}{y}$ . Hãy in ra $x \cdot y^{- 1} mod 998244353$ , trong đó $y^{- 1}$ là số nguyên thỏa mãn $y \cdot y^{- 1} \equiv 1 (\mod 998244353)$ .

Dữ liệu vào

Dòng duy nhất chứa một số nguyên $n$ .

Dữ liệu ra

In ra xác suất cần tìm theo modulo $998244353$ .

Ràng buộc

$1 \leq n \leq 2 \cdot 10^{5}$

Ví dụ

Input	Output	Giải thích
2	748683265	Xác suất thực là $\frac{1}{4}$ : chỉ khi xây cả hai tháp tại thị trấn $1$ và $2$ (xác suất $\frac{1}{4}$ ) thì đặt công suất bằng $1$ cho cả hai là thoả mãn.
3	748683265	Xác suất thực là $\frac{1}{4} = \frac{2}{8}$ : hai cấu hình thoả mãn — xây cả ba tháp với công suất $1$ , hoặc chỉ xây tháp tại $2$ với công suất $2$ .
5	842268673	Xác suất thực là $\frac{5}{32}$ . Ví dụ nếu các tháp được xây tại thị trấn $2, 4, 5$ , có thể đặt công suất tháp $2$ là $2$ , tháp $4$ và $5$ là $1$ .
200000	202370013	Trường hợp lớn nhất.

Bình luận

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