#1970. 国际象棋

    ID: 1970 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>CTT赛事:contest315来源:qoj.ac数据:公开样例动态规划数学

国际象棋

国际象棋

题目描述

标题: 国际象棋 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

英国之王 CauchySheep 最近在研究国际象棋。CauchySheep 认为棋盘太小了,所以他自创了一套规则:

在本题中,国际象棋的棋盘是一个 n×m 的网格,第 i(1≤i≤n) 行第 j(1≤j≤m) 个格子简记为 (i,j) 。为了简化问题,棋盘上只有一枚棋子:骑士。

现在 CauchySheep 将骑士放在 (sx,sy) ,然后开始随机游走。具体地,每个回合,假设骑士当前在 (x,y) ,则它:

  • 有 p1 的概率走到 (x−2,y−1) 。
  • 有 p2 的概率走到 (x−1,y−2) 。
  • 有 p3 的概率走到 (x+1,y−2) 。
  • 有 p4 的概率走到 (x+2,y−1) 。
  • 有 p5 的概率走到 (x+2,y+1) 。
  • 有 p6 的概率走到 (x+1,y+2) 。
  • 有 p7 的概率走到 (x−1,y+2) 。
  • 有 p8 的概率走到 (x−2,y+1) 。

当骑士走出棋盘时,游戏就结束了。

现在 CauchySheep 想要知道游戏期望经过多少个回合结束。CauchySheep 当然会做这个题,但是他想考考你。

输入格式

从标准输入读入数据。

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

第二行 8 个正整数 w1,w2,⋯,w8 用于计算 p , pi=wi∑j=18wj 。

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

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

输出格式

输出到标准输出中。

对于每个询问,输出一行一个整数表示答案在模 998244353 意义下的值。具体地,假设答案化成既约分数后是 pq ,则你只需要输出 pq−1mod998244353 的值即可。

样例数据

样例输入

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

样例输出

1
332748119

样例解释

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

当 (sx,sy)=(1,1) 时,答案为 43 。

样例输入

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

样例输出

691709817
186871978
807608945
374193381

样例解释

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

子任务

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

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

  • 子任务 1(10 分):n,m≤20;
  • 子任务 2(10 分):n,m≤50;
  • 子任务 3(20 分):n,m≤80,q=1;
  • 子任务 4(20 分):n,m≤80;
  • 子任务 5(20 分):m 是偶数;
  • 子任务 6(20 分):没有附加限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 3
1 1 1 1 1 1 1 1
2
2 2
1 1
1
332748119

样例 2

8 8
1 2 3 4 5 6 7 8
4
1 2
3 4
5 6
7 8
691709817
186871978
807608945
374193381