#P3281. [SCOI2013] 数数

    ID: 4792 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>字符串2013四川数位 dp进制

[SCOI2013] 数数

题目描述

Fish 是一条生活在海里的鱼,有一天他很无聊,就开始数数玩。他数数玩的具体规则是:

  1. 确定数数的进制B

  2. 确定一个数数的区间[L, R]

  3. 对于[L, R] 间的每一个数,把该数视为一个字符串,列出该字符串的每一个(连续的)子串对应的B进制数的值。

  4. 对所有列出的数求和。现在Fish 数了一遍数,但是不确定自己的结果是否正确了。由于[L, R] 较大,他没有多余精力去验证是否正确,你能写一个程序来帮他验证吗?

输入格式

输入包含三行。

第一行仅有一个数B,表示数数的进制。

第二行有N +1 个数,第一个数为N,表示数L 在B 进制下的长度为N,接下里的N个数从高位到低位的表示数L 的具体每一位。

第三行有M+ 1 个数,第一个数为M,表示数R 在B 进制下的长度为M,接下里的M个数从高位到低位的表示数R 的具体每一位。

输出格式

输出仅一行,即按照Fish 数数规则的结果,结果用10 进制表示,由于该数可能很大,输出该数模上20130427的模数。

数据中有 r<lr<l 的情况,输出的是 ans[r+1,l1]mod20130427-ans[r+1,l-1]\bmod 20130427

10
3 1 0 3
3 1 0 3
120

提示

【样例解释】

[103, 103] 之间仅有数103,该数的所有子串包括1, 10, 103, 0, 03, 3,其和为120。

【数据范围与约定】

20% 数据,0 <= L <= R <= 10^5。

50% 数据,2 <= B <= 1000,1 <= N,M <= 1000。

100% 数据,2 <= B <= 10^5,1 <= N,M <= 10^5。