UOJ Logo Universal Online Judge

UOJ

#141. 【UER #4】量子态的棋盘

统计

很久很久以前,有一个棋盘加入了 UOJ 群。

这天,在它讨论“一个棋盘应该怎么对偶”的时候一不小心被删除了,变成了量子态的棋盘。

突然间,它发现本来在它身上记录的东西全都变成量子态了。这让它的主人——著名的物理专家 Picks 博士非常烦恼:要知道这个棋盘可以他非常重要的试验道具。

于是他来找你帮忙尽可能地还原这个棋盘。

已知这个棋盘的大小是 $n \times m$ ,每一个格子的权值都是 $1$ 或者 $-1$ 。这个棋盘左上角格子的上方是入口,下边界和右边界是出口。

当 Picks 博士从左上角上方放入一个小球的时候,这个小球在这个棋盘中会以如下的方式运行:

如果当前小球所在的格子的权值是 $1$,那么小球将会从这个格子的右边界出去,否则它会从这个格子的下边界出去。在小球离开这个格子之后,这个格子的权值会变成原来的相反数,即 $1$ 变成 $-1$,$-1$ 变成 $1$。

Picks 博士的实验中的一步是这样的:他会依次往棋盘的左上角放入$K$个小球,每一个小球都是在前一个小球离开棋盘后再放入。当小球离开棋盘后,它会直接掉到地上。为了避免满地小球的情况, Picks 在一些出口下面挂了篮子,如果小球从挂了篮子的出口处离开棋盘,那么它会被篮子接住,否则它还是会掉到地上。

Picks 博士进行了 $Q$ 这样的试验,为了避免麻烦,任意两次实验的棋盘大小,放入小球个数,篮子的位置都是完全一样,他只更改了初始棋盘上的数字。但是因为实验结果被打杂的 jiry_2 吃掉了,所以他现在只记得第 $i$ 次试验接到的小球数目在区间 $[L_i,R_i]$ 内。

现在,Picks 博士告诉了你棋盘的大小,放入小球的个数,篮子的位置,以及每一次实验的 $L_i$ 和 $R_i$,他想要拜托你算出来每一次试验有多少种可能的棋盘是满足条件的。

输入格式

第一行是三个整数 $n,m,K$ ,分别表示棋盘的行数、列数以及每一次实验放入的小球个数。保证有 $n,m\geq 1$ 和 $K \geq 0$。

第二行包含了一个长度为 $n$ 的 01 串,第 $i$ 个字符是 1 表示第 $i$ 行的最右端挂了一个篮子,否则表示没有篮子。

第三行包含了一个长度为 $m$ 的 01 串,第 $i$ 个字符是 1 表示第 $i$ 列的最下端挂了一个篮子,否则表示没有篮子。

第四行包含了一个正整数 $Q$,表示实验的次数。

接下来 $Q$ 行,每行是两个整数 $L_i,R_i\ (0 \leq L_i \leq R_i \leq K)$ 表示 Picks 博士提供的试验的结果。

输出格式

共$Q$行,对于每一次试验你都需要输出一个整数,表示满足实验结果的不同棋盘的个数。两个棋盘时不同的当且仅当存在$i,j$使得两个棋盘第 $i$ 行第 $j$ 列的权值不同。

答案可能很大,你只需要输出答案对 $998244353(7\times 17 \times 2^{23}+1$,一个质数$)$ 取模后的结果。

样例一

input

3 3 5
111
111
2
0 3
4 5

output

0
512

explanation

可以发现,无论棋盘时什么样的,篮子总是可以接到所有的小球,所以对于所有可能的 $2^{nm}=512$ 种方案,Picks都能接到 $5$ 个小球。

样例二

input

1 2 2
1
10
3
0 0
1 1
2 2

output

0
2
2

explanation

一共有四种棋盘:

  1. 初始棋盘是 $1,1$。第一个小球会从棋盘右边界运行出去被篮子接到。此时棋盘变成了 $-1,-1$,第二个小球会从第一列的下方运行出去被篮子接到,此时棋盘变成了 $1,-1$。
  2. 初始棋盘是 $1,-1$。第一个小球会从棋盘第二列的下方运行出去掉到地上。此时棋盘变成了 $-1,1$,第二个小球会从第一列的下方运行出去被篮子接到,此时棋盘变成了 $1,1$。
  3. 初始棋盘是 $-1,1$。第一个小球会从棋盘第一列的下方运行出去被篮子接到。此时棋盘变成了 $1,1$,第二个小球会从棋盘的右边界运行出去被篮子接到,此时棋盘变成了 $-1,-1$。
  4. 初始棋盘是 $-1,-1$。第一个小球会从棋盘第一列的下方运行出去被篮子接到。此时棋盘变成了 $1,-1$,第二个小球会从第二列的下方运行出去掉到地上,此时棋盘变成了 $-1,1$。

所以接到两个球和接到一个球的方案各有两个。

样例三

input

4 4 15
1011
1000
2
1 6
7 15

output

29696
35840

限制与约定

测试点编号 $n,m$的规模 $K$的规模 $Q$的规模
1, 2$n,m \leq 4$$K \leq 10$ $Q \leq 100000$
3, 4
5, 6$K \leq 10^{18}$
7, 8
9, 10$n,m \leq 7$$Q \leq 1000$
11, 12$Q \leq 100000$
13, 14$n,m \leq 9$$Q \leq 1000$
15, 16$Q \leq 100000$
17, 18$n,m \leq 10$$Q \leq 1000$
19, 20$Q \leq 100000$

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载