#PQJ2470x15142. QOJ 2470_15142

    ID: 2828 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SCOI 2011动态规划数位DP

QOJ 2470_15142

lxhgww 非常喜欢数字游戏,他发现,很多数都可以表示成两个相互反转的数之和,他把这个现象称为数的“镜像拆分”。比如 66 共有五种镜像拆分方法:

66=15+51
66=24+42
66=33+33
66=42+24
66=51+15

注意,前导 0 是不允许的,所以 66

60 + 06 不算做合法的镜像拆分。

现在 lxhgww 想知道,在 𝐾 进制下,对于在 [ 𝐴 , 𝐵 ] 区间内的数,其镜像拆分的方案数之和是多少?

输入格式

输入的第一行是一个数 𝐾 。

输入的第二行是一个数 𝑛 ,表示数字 𝐴 的长度。

接下来 𝑛 行,表示 𝐴 从低位开始的每一位数字。

然后是一个数 𝑚 ,表示数字 𝐵 的长度。

接下来 𝑚 行,表示 𝐵 从低位开始的每一位数字。

输出格式

输出一行,包含一个整数,表示镜像拆分的方案数之和。由于这个答案非常大,只需要输出这个答案除以 20110521 的余数。

样例数据 样例 1 输入 10 2 6 6 2 6 6 样例 1 输出 5 样例 2 输入 10 1 1 4 0 0 0 1 样例 2 输出 410 子任务

对于 20 % 的数据, 2 ≤ 𝐾 ≤ 100 , 1 ≤ 𝑛 , 𝑚 ≤ 100 。

对于 50 % 的数据, 2 ≤ 𝐾 ≤ 10 3 , 1 ≤ 𝑛 , 𝑚 ≤ 10 3 。

对于 100 % 的数据, 2 ≤ 𝐾 ≤ 10 5 , 1 ≤ 𝑛 , 𝑚 ≤ 10 5 。

对于所有的数据, 0 < 𝐴 ≤ 𝐵 ,且 𝐴 , 𝐵 的每一位数字都在 [ 0 , 𝐾 − 1 ] 的范围内,没有前导 0 。