← 返回题目列表

Codeforces · 1452/D

D. 无线电塔

中文机器翻译题面 查看原题

坐标线上有 $$$n + 2$$$ 个城镇,编号从 $$$0$$$ 到 $$$n + 1$$$。第 $$$i$$$ 个城镇位于 $$$i$$$ 点。

您在每个城镇 $$$1, 2, \dots, n$$$ 建造一座无线电塔,概率为 $$$\frac{1}{2}$$$(这些事件是独立的)。之后,您希望将每个塔上的信号功率设置为从 $$$1$$$ 到 $$$n$$$ 的某个整数(信号功率不一定相同,但也不一定不同)。来自城镇 $$$i$$$ 的信号塔信号功率 $$$p$$$ 到达每个城市 $$$c$$$,使得 $$$|c - i| <p$$$。

建造塔后,您希望通过以下方式选择信号功率:

- 城镇$$$0$$$和$$$n + 1$$$没有从无线电塔收到任何信号;
- 城镇 $$$1, 2, \dots, n$$$ 每个城镇仅从一个无线电塔获取信号。

例如,如果$$$n = 5$$$,并且您在城镇$$$2$$$、$$$4$$$和$$$5$$$建有信号塔,则可以将城镇$$$2$$$的信号塔信号功率设置为$$$2$$$,将城镇$$$4$$$和$$$5$$$的信号功率设置为$$$1$$$。这样,城镇 $$$0$$$ 和 $$$n + 1$$$ 不会从任何塔楼获得信号,城镇 $$$1$$$、$$$2$$$ 和 $$$3$$$ 从城镇 $$$2$$$ 的塔楼获取信号,城镇 $$$4$$$ 从城镇 $$$4$$$ 的塔楼获取信号,城镇 $$$5$$$ 从城镇的塔楼获取信号$$$5$$$。

计算在建造塔后,您将有办法设置信号功率以满足所有约束的概率。

输入

输入的第一行(也是唯一的一行)包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

输出

打印一个整数 — 有一种方法可以设置信号功率以满足所有约束的概率,以 $$$998244353$$$ 为模。

形式上,概率可以表示为不可约分数 $$$\frac{x}{y}$$$。您必须打印 $$$x \cdot y^{-1} \bmod 998244353$$$ 的值,其中 $$$y^{-1}$$$ 是一个整数,使得 $$$y \cdot y^{-1} \bmod 998244353 = 1$$$。

示例

输入 #1

2

输出 #1

748683265

输入 #2

3

输出 #2

748683265

输入 #3

5

输出 #3

842268673

输入#4

200000

输出#4

202370013

注意

第一个示例的真正答案是 $$$\frac{1}{4}$$$:

- 以 $$$\frac{1}{4}$$$ 的概率,塔楼建在 $$$1$$$ 和 $$$2$$$ 两个城镇中,因此我们可以将它们的信号功率设置为 $$$1$$$。

第二个示例的真正答案是 $$$\frac{1}{4}$$$:

- 概率为 $$$\frac{1}{8}$$$,塔建在城镇 $$$1$$$、$$$2$$$ 和 $$$3$$$ 上,因此我们可以将它们的信号功率设置为 $$$1$$$;
- 以 $$$\frac{1}{8}$$$ 的概率,$$$2$$$ 镇中只会建造一座塔,我们可以将其信号功率设置为 $$$2$$$。

第三个示例的真正答案是 $$$\frac{5}{32}$$$。请注意,尽管前面的解释对所有塔使用了相同的信号功率,但事实并非如此。例如,如果$$$n = 5$$$,并且信号塔建在城镇$$$2$$$、$$$4$$$和$$$5$$$,则可以将城镇$$$2$$$的信号塔信号功率设置为$$$2$$$,将城镇$$$4$$$和$$$5$$$的信号塔信号功率设置为$$$1$$$。