【UR #23】国王出游 - 题目 - Universal Online Judge

跳蚤国王兴致大发，在刚建好的跳蚤利亚上游玩！

跳蚤利亚的布局是网格状，因为它太大了，我们把它看成一个坐标系，其中 $(0, 0)$ 是跳蚤国王的城堡，y 轴正方向是正北，x 轴正方向是正东。

跳蚤国王初始在 $(x_{0}, y_{0})$ 视察工作，每一秒，假设跳蚤国王在 $(x, y)$ ，就会等概率随机走到 $(x + A, y), (x - B, y), (x, y + C), (x, y - D)$ 中的一个位置。

跳蚤国王计划走 $T$ 秒，如果最终他走到了 $(x_{T}, y_{T})$ ，那么这次出游，他的愉悦度就是 $x_{T}^{n} y_{T}^{m}$ ，即 $x_{T}$ 的 $n$ 次方乘以 $y_{T}$ 的 $m$ 次方。

国王想知道，他这次出游愉悦度的期望对 $998244353$ 取模后的结果。

一行九个整数 $n, m, T, x_{0}, y_{0}, A, B, C, D$ ，含义见上。

一行一个整数，表示期望对 $998244353$ 取模后的结果。可以证明答案一定可以被表示为 $\frac{a}{b}$ 的形式，其中 $gcd (a, b) = 1$ ，你需要输出整数 $c$ 满足 $b c \equiv a mod 998244353$ 。

2 3 2 0 1 1 1 2 3

748683270

一共有 $16$ 种可能。

	$(1, 0)$	$(- 1, 0)$	$(0, 2)$	$(0, - 3)$
$(1, 0)$	$(2, 1) : 4$	$(0, 1) : 0$	$(1, 3) : 27$	$(1, - 2) : - 8$
$(- 1, 0)$	$(0, 1) : 0$	$(- 2, 1) : 4$	$(- 1, 3) : 27$	$(- 1, - 2) : - 8$
$(0, 2)$	$(1, 3) : 27$	$(- 1, 3) : 27$	$(0, 5) : 0$	$(0, 0) : 0$
$(0, - 3)$	$(1, - 2) : - 8$	$(- 1, - 2) : - 8$	$(0, 0) : 0$	$(0, - 5) : 0$

愉悦度的期望为： $\frac{84}{16} = \frac{21}{4}$ ，而 $4 \times 748683270 \equiv 21 (\mod 9) 98244353$ 。

见附件下载。

子任务编号	$n, m \leq$	$T \leq$	特殊性质	分值
$1$	$2000$	$2000$	无	$20$
$2$	$100000$	$10^{9}$	$1$	$20$
$3$		$100000$	$2, 3$	$10$
$4$		$10^{9}$	$2, 3$	$10$
$5$			$2$	$10$
$6$			$3$	$20$
$7$			无	$10$

特殊性质 $1$ ： $A = B = C = D = 1$ 。

特殊性质 $2$ ： $A \neq B, C \neq D$ 。

特殊性质 $3$ ： $x_{0} = y_{0} = 0$ 。

对于所有数据， $0 \leq n, m \leq 10^{5}, 0 \leq T \leq 10^{9}, 0 \leq x_{0}, y_{0}, A, B, C, D < 998244353$ 。

时间限制： $5s$

空间限制： $512MB$

Universal Online Judge