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

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cz_xuyixuan

题目描述

英国之王 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

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

样例输出 1

1
332748119

样例解释 1

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

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

样例输入 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

样例解释 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 分):没有附加限制。