#CW58. 拓展位运算(radix)

拓展位运算(radix)

题目描述

在二进制中,按位与和按位或都是对每一位分别进行的运算。本题把每一位可取的数字从 0,10,1 扩展到 0,1,…,k−10,1,\dots,k-1,并允许运算规则由输入的真值表决定。

给定进制 kk 以及两个大小均为 k×kk\times k 的表 A,BA,B。表的行和列都从 00 开始编号。对于两个 kk 进制数位 u,vu,v,其中 0≤u,v<k0\le u,v<k,运算规则定义为:u∧vu\wedge v 的结果为查表值 Au,vA_{u,v},u∨vu\vee v 的结果为查表值 Bu,vB_{u,v}。

这里第一下标对应第一个数位,第二下标对应第二个数位;因此即使 Au,vA_{u,v} 与 Av,uA_{v,u} 不同,题目也仍然按照输入表的方向计算,运算不一定满足交换律。符号 ∧\wedge 和 ∨\vee 分别表示本题定义的广义按位与和广义按位或。

对两个非负整数进行运算时,先分别写成 kk 进制,并在位数较短的数的左侧补足前导 00,直到两数位数相同;然后对每一列对应的数位查表,得到结果的每一位。例如在 k=3k=3 时,1023102_3 与 21321_3 要先对齐为 1023102_3 和 0213021_3。三列对应的数位分别是 (1,0)(1,0)、(0,2)(0,2)、(2,1)(2,1),所以按位与结果的三位依次为 A1,0,A0,2,A2,1A_{1,0},A_{0,2},A_{2,1}。

现在给定三个不含前导 00 的 kk 进制正整数 n,x,yn,x,y。需要统计所有满足 1≤a≤n1\le a\le n 的整数 aa,只要下面两个条件中至少一个成立,就将它计入答案:

  • a∧x=ya\wedge x=y;
  • a∨x=ya\vee x=y。

如果同一个 aa 同时满足两个条件,也只能计数一次。

输入格式

从 radix.in 文件读入数据。

第一行输入 kk。接下来 kk 行输入表 AA,再接下来 kk 行输入表 BB。最后三行依次输入 kk 进制正整数 n,x,yn,x,y,均不含前导零。

输出格式

将结果输出到 radix.out 文件。

输出一个整数,表示满足条件的 aa 的数量。

样例 1 输入

2
0 0
0 1
0 1
1 1
111
101
101

样例 1 输出

4

样例 2 输入

3
0 0 0
0 1 1
0 1 2
0 1 2
1 1 2
2 2 2
20
1
1

样例 2 输出

4

数据范围

对于全部数据,满足 2≤k≤102\le k\le 10;A,BA,B 的每个元素属于 [0,k−1][0,k-1];1≤n,x,y≤1061\le n,x,y\le 10^6,并且输入表示合法的 kk 进制数。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 25 1∼51\sim 5 n≤100n\le 100
2 6∼106\sim 10 n≤1000n\le 1000
3 11∼1511\sim 15 n≤104n\le 10^4
4 16∼2016\sim 20 n≤106n\le 10^6