【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^ny_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$ 满足 $bc\equiv a\bmod 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\pmod 998244353$。

见附件下载。

子任务编号	$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\lt 998244353$。

时间限制：$\texttt{5s}$

空间限制：$\texttt{512MB}$

Universal Online Judge