传统题 1000ms 512MiB

不带壳

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小周很喜欢 Dyck 路。有一天,她被邀请去到一个二维平面上游玩,所以需要规划一下游玩路径。因为小周是来游玩的,她的每一步必定停留在一个景点上。她想要规划出一条 Dyck 路作为自己的路径,但这些景点的位置有些特殊。具体地,一个点 (x,y)(x, y) 为景点当且仅当 xx 为非负整数且 y{0,1}y \in \{0, 1\}。也就是说,这些景点在平面上排成了两排。小周最开始位于景点 s=(0,0)s = (0, 0)

在这样一个平面上行走实在是太简单了,就连小周都失去了规划路径的兴趣,任由概率带领她前行;她也不希望游览两次相同的景点。小周会从 ss 开始,每次在和当前所在景点四联通的景点中均匀随机选取一个未被经过的景点,并走过去。如果不存在这样的景点,那么小周就会结束这一次游玩。令小周可能行走的一条路径为 WW,记 p(W)p(W) 为最终小周行走的路径为 WW 的概率,并记 W\lvert W \rvertWW 的长度或小周总共移动的次数,d(W)d(W) 为过程中景点 xx 坐标的最大值。

在出发前,小周听说 xx 坐标为 x0x_0 的两个景点有很美丽的风景,但她不希望自己很累,不想走多于 nn 步。所以她就想知道,她走出一条 Wn,d(W)=x0\lvert W \rvert\le n, d(W) = x_0 的路径 WW 的概率,也就是

Wn,d(W)=x0p(W)\sum_{\lvert W \rvert\le n, d(W) = x_0} p(W)

但小周的数学不太好,她不会算这个值,于是她来求助你了。小周保证答案是有理数,她也知道这个分数的分子分母都可能很大,所以你只需要输出这个分数对 998244353998244353 取模的结果即可。具体地,假设答案为 p/qp/q,其中 gcd(p,q)=1\gcd(p, q) = 1,那么取 qrp(mod998244353)qr \equiv p \pmod {998244353},你只需要输出 rmod998244353r\bmod 998244353。可以证明 rr 必定存在。

输入格式

一行两个整数 n,x0n, x_0

输出格式

一行一个整数,表示答案。

样例输入 #1

10 6

样例输出 #1

988495873

样例 #2

样例输入 #2

65 32

样例输出 #2

394183784

样例 #3

样例输入 #3

191981 114514

样例输出 #3

427827207

数据范围

Subtask 分值 特殊性质
1 5 x05x_0\le 5
2 x0105,n=2x0+1x_0 \le 10^5, n = 2x_0 + 1
3 10 n=2x0+1n = 2x_0 + 1
4 x0105x_0\le 10^5
5 25 x0107x_0 \le 10^7
6 45

对所有数据,2x01092 \le x_0 \le 10^{9}x0+3n2x0+1x_0 + 3 \le n\le 2x_0 + 1

[YDRG#012] 云斗学院英雄纪 · 云斗三周年限定 Golden Round

未参加
状态
已结束
规则
IOI
题目
7
开始于
2025-11-21 8:00
结束于
2025-11-26 20:00
持续时间
5 小时
主持人
参赛人数
142