题目：
Fish 是一条生活在海里的鱼，有一天他很无聊，就开始数数玩。他数数玩的具体规则是：
确定数数的进制$B$
确定一个数数的区间$[L, R]$
对于$[L, R] $间的每一个数，把该数视为一个字符串，列出该字符串的每一个（连续的）子串对应的$B$进制数的值。
对所有列出的数求和。现在Fish 数了一遍数，但是不确定自己的结果是否正确了。由于$[L, R] $较大，他没有多余精力去验证是否正确，你能写一个程序来帮他验证吗？
非常恶心的一道数位$DP$
首先是数位$DP$的常规套路，用$[1,R]$的答案减去$[1,L-1]$的答案
对于一个$B$进制数$S$，令$f_{S}$表示$S$所有后缀串所表示数的和，$l_{S}$表示数$S$的位数，现在在它末尾填上一个数$x$，则$F_{Sx}=F_{S}*B+x*(l_{S}+1)$
令$g_{S}$表示$S$所有子串所表示数的和，则$g_{Sx}=g_{S}*B+F_{Sx}$
我们要对$[1,S]$里的所有数进行统计，令$F_{i,0}$表示从高到低遍历到了第i位，未达到上限的所有数的$f_{x}$，$F_{i,1}$是达到上限的
可得$F_{i+1,0}=\sum_{x=1}^{B}(F_{i,0}*B+x*\sum (l_{S}+1))=B^{2}F_{i,0}+\frac{B(B-1)}{2}\sum (l_{S}+1)$
而$F_{i,1}$转移到$F_{i+1,0}$的也是类似的
显然我们还要维护一个数组$L_{i}$，表示前i位数中出现的数的$l_{x}$之和
因为要加上$\sum (l_{S}+1)$，还需要维护一个$Sum_{i}$，表示前i位数中出现的数的数量
这两个数组都很好维护
最后就是统计答案了，令$G_{i,0}$表示从高到低遍历到了第i位，未达到上限的所有数的$g_{x}$之和，$G_{i,1}$是达到上限的
因为每个$G_{i,0}$都有$B$次被转移，所以$G_{i+1,0}=B\cdot G_{i,0}+F_{i+1,0}$
而$G_{i,1}$转移到$G_{i+1,0}$的情况也是类似的
注意前导零的处理，我的方法是每遍历到新的一位，1~B每个数都还会作为一个新数的开头(除了第一位)，把都加入状态里即可
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 101000
#define N2 4201
#define M1 120
#define ll long long
#define dd double
#define uint unsigned int
#define idx(X) (X-'0')
using namespace std; const int mod=;
int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
int n,m,B;
int f[N1][],g[N1][],s[N1][],l[N1][];
ll solve(int *a,int len)
{
memset(f,,sizeof(f));
memset(g,,sizeof(g));
memset(l,,sizeof(l));
memset(s,,sizeof(s));
ll ans=;
s[][]=a[]-,s[][]=;
l[][]=a[]-,l[][]=;
f[][]=1ll*a[]*(a[]-)/%mod;
f[][]=a[];
g[][]=f[][],g[][]=f[][];
for(int i=;i<len;i++)
{
s[i+][]=(1ll*s[i][]*B%mod + 1ll*s[i][]*a[i+]%mod + B-)%mod;
s[i+][]=s[i][];
l[i+][]=(1ll*(l[i][]+s[i][])*B%mod + 1ll*(l[i][]+s[i][])*a[i+]%mod + B-)%mod;
l[i+][]=(l[i][]+s[i][]);
f[i+][]=(1ll*f[i][]*B%mod*B%mod + 1ll*f[i][]*a[i+]%mod*B%mod + 1ll*(1ll*B*(B-)/%mod)*(l[i][]+s[i][]+)%mod + 1ll*(1ll*a[i+]*(a[i+]-)/%mod)*(l[i][]+s[i][])%mod)%mod;
f[i+][]=(1ll*f[i][]*B%mod + 1ll*a[i+]*(l[i][]+)%mod)%mod;
g[i+][]=(1ll*g[i][]*B%mod + 1ll*g[i][]*a[i+]%mod + f[i+][])%mod;
g[i+][]=(g[i][] + f[i+][])%mod;
}
return (g[len][]+g[len][])%mod;
}
int a[N1],b[N1],tmp[N1]; int main()
{
scanf("%d",&B);
scanf("%d",&n);
for(int i=n;i>=;i--)
tmp[i]=gint();
scanf("%d",&m);
for(int i=;i<=m;i++)
b[i]=gint();
tmp[]--;int k=;
while(tmp[k]<)
tmp[k]+=B,tmp[k+]--,k++;
if(tmp[n]==) n--;
for(int i=;i<=n;i++)
a[i]=tmp[n-i+];
ll ans1=solve(a,n);
ll ans2=solve(b,m);
printf("%lld\n",((ans2-ans1)%mod+mod)%mod);
return ;
}