A6095. 「SCOI2011」镜像拆分
编程题
省选/NOI-
知识点
题目描述
lxhgww 非常喜欢数字游戏，他发现，很多数都可以表示成两个相互反转的数之和，他把这个现象称为数的“镜像拆分”。比如 $66$ 共有五种镜像拆分方法：
- $66=15+51$
- $66=24+42$
- $66=33+33$
- $66=42+24$
- $66=51+15$
注意，前导 $0$ 是不允许的，所以 $66=60+06$ 不算做合法的镜像拆分。
现在 lxhgww 想知道，在 $K$ 进制下，对于在 $[A,B]$ 区间内的数，其镜像拆分的方案数之和是多少？
- $66=15+51$
- $66=24+42$
- $66=33+33$
- $66=42+24$
- $66=51+15$
注意，前导 $0$ 是不允许的，所以 $66=60+06$ 不算做合法的镜像拆分。
现在 lxhgww 想知道，在 $K$ 进制下，对于在 $[A,B]$ 区间内的数，其镜像拆分的方案数之和是多少？
输入格式
输入的第一行是一个数 $K$ 。
输入的第二行是一个数 $n$ ，表示数字 $A$ 的长度。
接下来 $n$ 行，表示 $A$ 从低位开始的每一位数字。
然后是一个数 $m$ ，表示数字 $B$ 的长度。
接下来 $m$ 行，表示 $B$ 从低位开始的每一位数字。
输入的第二行是一个数 $n$ ，表示数字 $A$ 的长度。
接下来 $n$ 行，表示 $A$ 从低位开始的每一位数字。
然后是一个数 $m$ ，表示数字 $B$ 的长度。
接下来 $m$ 行，表示 $B$ 从低位开始的每一位数字。
输出格式
输出一行，包一个整数，表示镜像拆分的方案数之和。由于这个答案非常大，只需要输出这个答案除以 $20110521$ 的余数。
输入输出样例
输入 #1
10 2 6 6 2 6 6
输出 #1
5
输入 #2
10 1 1 4 0 0 0 1
输出 #2
410
说明/提示
对于 $20\%$ 的数据， $2 \le K \le 100 , 1 \le n , m \le 100$ 。
对于 $50\%$ 的数据， $2 \le K \le 10^3 , 1 \le n , m \le 10^3$ 。
对于 $100\%$ 的数据， $2 \le K \le 10^5 , 1 \le n , m \le 10^5 , 0<A \le B$ ，且 $A$ ， $B$ 的每一位数字都在 $[0,K-1]$ 的范围内，没有前导 $0$ 。
对于 $50\%$ 的数据， $2 \le K \le 10^3 , 1 \le n , m \le 10^3$ 。
对于 $100\%$ 的数据， $2 \le K \le 10^5 , 1 \le n , m \le 10^5 , 0<A \le B$ ，且 $A$ ， $B$ 的每一位数字都在 $[0,K-1]$ 的范围内，没有前导 $0$ 。