LibreOJ

3080 「2019 集训队互测 Day 5」国际象棋

内存限制：512 MB 时间限制：3000 ms

题目描述

英国之王 CauchySheep 最近在研究国际象棋。CauchySheep 认为棋盘太小了，所以他自创了一套规则： 在本题中，国际象棋的棋盘是一个 $n\times m$ 的网格，第 $i(1\le i\le n)$ 行第 $j(1\le j\le m)$ 个格子简记为 $(i, j)$ 。为了简化问题，棋盘上只有一枚棋子：骑士。 现在 CauchySheep 将骑士放在 $(sx, sy)$ ，然后开始随机游走。具体地，每个回合，假设骑士当前在 $(x,y)$ ，则它： - 有 $p_1$ 的概率走到 $(x-2,y-1)$ 。 - 有 $p_2$ 的概率走到 $(x-1,y-2)$ 。 - 有 $p_3$ 的概率走到 $(x+1,y-2)$ 。 - 有 $p_4​$ 的概率走到 $(x+2,y-1)​$ 。 - 有 $p_5$ 的概率走到 $(x+2,y+1)$ 。 - 有 $p_6$ 的概率走到 $(x+1,y+2)$ 。 - 有 $p_7$ 的概率走到 $(x-1,y+2)$ 。 - 有 $p_8$ 的概率走到 $(x-2,y+1)$ 。 当骑士走出棋盘时，游戏就结束了。 现在 CauchySheep 想要知道游戏期望经过多少个回合结束。CauchySheep 当然会做这个题，但是他想考考你。

输入格式

从标准输入读入数据。

第一行两个正整数 $n,m$ 。

第二行 $8$ 个正整数 $w_1, w_2, \cdots, w_8$ 用于计算 $p$ ， $p_i = \frac{w_i}{\sum_{j=1}^8 w_j}$ 。

第三行一个正整数 $q$ 表示询问个数。

接下来 $q$ 行，每行两个正整数 $sx, sy$ 表示起始坐标。

输出格式

输出到标准输出中。

对于每个询问，输出一行一个整数表示答案在模 $998244353$ 意义下的值。具体地，假设答案化成既约分数后是 $\frac{p}{q}$ ，则你只需要输出 $pq^{-1}\bmod 998244353$ 的值即可。

样例 1

当 $(sx, sy) = (2, 2)$ 时，骑士不管怎么走都会一步走出棋盘，答案为 $1$ 。

当 $(sx, sy) = (1, 1)$ 时，答案为 $\frac{4}{3}$ 。

样例 2

我有一个绝妙的解释，可是这里地方太小，写不下。

数据范围与提示

对于所有数据，满足 $2\le n, m\le 200, 1\le w_i\le 100, 1\le q\le nm$，询问的 $(sx, sy)$ 互不相同。

共有六个子任务，每个子任务的特殊限制和分值如下：

  • 子任务 $1$（$10$ 分）：$n, m\le 20$；
  • 子任务 $2$（$10$ 分）：$n, m\le 50$；
  • 子任务 $3$（$20$ 分）：$n, m\le 80$，$q=1$；
  • 子任务 $4$（$20$ 分）：$n, m\le 80$；
  • 子任务 $5$（$20$ 分）：$m$ 是偶数；
  • 子任务 $6$（$20$ 分）：没有附加限制。

样例

样例输入 1

3 3
1 1 1 1 1 1 1 1
2
2 2
1 1

样例输出 1

1
332748119

样例输入 2

8 8
1 2 3 4 5 6 7 8
4
1 2
3 4
5 6
7 8

样例输出 2

691709817
186871978
807608945
374193381